Pagini recente » Cod sursa (job #2331873) | Cod sursa (job #2809414) | Cod sursa (job #3247725) | Monitorul de evaluare | Cod sursa (job #2917626)
#include <fstream>
#include <vector>
#define MAX 100010
using namespace std;
vector<int> children[MAX];
int parent[MAX];
int d[MAX];
int diam[MAX];
int root = 1;
void init_distances(int node){
int ans = -1;
for(auto x:children[node]){
init_distances(x);
ans = max(ans, d[x]);
}
d[node] = ans + 1;
}
void compute_diams(int node){
if(d[node] == 0)
return;
else{
int max1 = -1;
int max2 = -1;
int child1, child2;
child1 = child2 = 0;
int max_diam = 0;
for(auto x:children[node]){
compute_diams(x);
max_diam = max(diam[x], max_diam);
if(d[x] >= max1){
child2 = child1;
child1 = x;
max1 = d[child1];
max2 = d[child2];
}
else if(d[x] >= max2){
child2 = x;
max2 = d[child2];
}
}
if(children[node].size() >= 2)
max_diam = max(2 + max1 + max2, max_diam);
else if(children[node].size() == 1)
max_diam = max(1 + max1, max_diam);
diam[node] = max_diam;
}
}
int main(){
ifstream fin;
ofstream fout;
fin.open("darb.in");
fout.open("darb.out");
int m, n, q, a, b;
fin >> n;
for(int i=1; i <= n - 1; ++i){
fin >> a >> b;
children[a].push_back(b);
parent[b] = a;
}
while(parent[root] != 0)
root = parent[root];
init_distances(root);
compute_diams(root);
// for(int i=1; i <= n; ++i){
// fout << i << ": " << diam[i] << ", ";
// }
fout << diam[root] + 1;
}