Pagini recente » Cod sursa (job #2227225) | Cod sursa (job #2168808) | Cod sursa (job #1637441) | Cod sursa (job #161734) | Cod sursa (job #2659894)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
const int maxV = 1e5;
vector <int> adjList[1 + maxV];
vector <int> dp;
int V;
int diameter;
void readGraph(){
fin >> V;
for(int e = 1; e < V; ++e){
int u, v;
fin >> u >> v;
adjList[u].push_back(v);
adjList[v].push_back(u);
}
dp.resize(1 + V);
}
void DFS(int node, int dad){
dp[node] = 1;
if(adjList[node].size() == 1 and dad == 0){
int adj = adjList[node].front();
DFS(adj, node);
dp[node] += dp[adj];
diameter = max(diameter, dp[node]);
}
else if(adjList[node].size() == 2 and dad){
int Max = 0;
for(const int &adj : adjList[node])
if(adj != dad){
DFS(adj, node);
Max = max(Max, dp[adj]);
}
dp[node] += Max;
diameter = max(diameter, dp[node]);
}
else {
int max1 = 0;
int max2 = 0;
for(const int &adj : adjList[node])
if(adj != dad){
DFS(adj, node);
if(dp[adj] >= max1)
max2 = max1, max1 = dp[adj];
else if(dp[adj] > max2)
max2 = dp[adj];
}
diameter = max(diameter, 1 + max1 + max2);
dp[node] += max1;
}
}
int main(){
readGraph();
DFS(1, 0);
fout << diameter << '\n';
}