Pagini recente » Cod sursa (job #374637) | Cod sursa (job #1661254) | Cod sursa (job #754253) | Cod sursa (job #1344370) | Cod sursa (job #1901539)
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n, i, t, h[N], st, dr, l, g[N], T[N];
bool o[N];
vector<int> G[N];
vector<int> diam;
void DFS_diam(int s) {
int m1, m2, a, b;
m1 = m2 = 0;
h[s] = 1;
g[s] = s;
for (auto x:G[s])
if (!h[x]) {
DFS_diam(x);
if (h[x] + 1 > h[s])
h[s] = h[x] + 1, g[s] = g[x]; //max depth
if (h[x] > m1) {
m2 = m1;
m1 = h[x];
b = a;
a = g[x];
} else if (h[x] > m2) m2 = h[x], b = g[x];
}
if (m2) {
if (l < m1 + m2 + 1) {
l = m1 + m2 + 1;
st = a;
dr = b;
}
} else {
if (l < m1 + 1) {
l = m1 + 1;
st = s;
dr = a;
}
}
}
void DFS(int s) {
o[s] = 1;
for (auto x:G[s])
if (!o[x]) {
T[x] = s;
DFS(x);
}
}
int main() {
freopen("darb.in", "r", stdin);
freopen("darb.out", "w", stdout);
int x, y;
t=1;
//scanf("%d", &t);
while (t--) {
scanf("%i", &n);
for (i = 1; i <= n; i++) G[i].clear();
memset(o, 0, (n + 1) * sizeof(bool));
for (i = 1; i < n; i++) {
scanf("%i%i", &x, &y);
G[x + 1].push_back(y + 1);
G[y + 1].push_back(x + 1);
}
DFS_diam(2);
l = 0;
DFS(st); //capetele diametrului
for (i = dr; i != st; i = T[i])
diam.push_back(i);
diam.push_back(st);
printf("%i", diam.size());
//DFS(dr);
}
return 0;
}