Pagini recente » Cod sursa (job #1024255) | Cod sursa (job #297691) | Cod sursa (job #758739) | Cod sursa (job #298335) | Cod sursa (job #2533573)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 100505;
int N, bestDown[NMAX], parent[NMAX];
bool visited[NMAX];
vector<int> G[NMAX];
void read() {
scanf("%d", &N);
int x, y;
for (int edgeIdx = 0; edgeIdx < N - 1; edgeIdx++) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
}
int dfs(int node) {
visited[node] = true;
int result = 0;
for (auto& neighbour : G[node]) {
if (!visited[neighbour]) {
parent[neighbour] = node;
result = max(result, dfs(neighbour));
}
}
int bestChildDown = -1, secondBestChildDown = -1;
for (auto& neighbour : G[node]) {
if (parent[neighbour] != node) {
continue;
}
// improve 1st child
if (bestChildDown == -1 || bestDown[bestChildDown] < bestDown[neighbour]) {
secondBestChildDown = bestChildDown;
bestChildDown = neighbour;
} else if (secondBestChildDown == -1 || bestDown[secondBestChildDown] < bestDown[neighbour]) {
secondBestChildDown = neighbour;
}
}
bestDown[node] = 1 + (bestChildDown == -1 ? 0 : bestDown[bestChildDown]);
result = max(result, bestDown[node]);
if (bestChildDown != -1 && secondBestChildDown != -1) {
result = max(result, 1 + bestDown[bestChildDown] + bestDown[secondBestChildDown]);
}
return result;
}
int main() {
freopen("darb.in", "r", stdin);
freopen("darb.out", "w", stdout);
read();
printf("%d\n", dfs(1));
return 0;
}