Pagini recente » Cod sursa (job #1284278) | Cod sursa (job #984555) | Cod sursa (job #2209564) | Cod sursa (job #3253997) | Cod sursa (job #1992395)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
int n, down[N], up[N], dep[N];
vector <int> g[N];
void dfsdown(int nod, int father) {
dep[nod] = dep[father] + 1;
for (auto fiu : g[nod])
if (fiu != father) {
dfsdown(fiu, nod);
down[nod] = max(down[nod], down[fiu] + 1);
}
}
void dfsup(int nod, int father, int best) {
if (father != 0) {
up[nod] = dep[nod] + best;
}
int ind_best = 0, mx1 = 0, mx2 = 0;
for (auto fiu : g[nod]) {
if (fiu != father) {
if (down[fiu] + 1 == down[nod]) {
ind_best = fiu;
}
if (down[fiu] + 1 > mx1) {
mx2 = mx1;
mx1 = down[fiu] + 1;
}
else if (down[fiu] + 1 > mx2) {
mx2 = down[fiu] + 1;
}
}
}
for (auto fiu : g[nod]) {
if (fiu != father) {
int upd = 0;
if (fiu == ind_best) {
upd = max(best, -dep[nod] + mx2);
}
else upd = max(best, -dep[nod] + mx1);
dfsup(fiu, nod, upd);
}
}
}
int main() {
ifstream cin("darb.in");
ofstream cout("darb.out");
cin >> n;
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfsdown(1, 0);
dfsup(1, 0, 0);
int diam = 0;
for(int i = 1; i <= n; ++i) {
diam = max(diam, up[i]);
diam = max(diam, down[i]);
}
cout << diam+1;
}