Pagini recente » Cod sursa (job #2755358) | Cod sursa (job #577763) | Cod sursa (job #1643888) | Cod sursa (job #2537227) | Cod sursa (job #2533577)
#include <cstdio>
#include <vector>
#include <functional>
#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));
}
}
vector<int> childCandidates;
for (auto& neighbour : G[node]) {
if (parent[neighbour] == node) {
childCandidates.push_back(bestDown[neighbour]);
}
}
if (childCandidates.size() >= 2) {
nth_element(childCandidates.begin(), childCandidates.begin() + 2, childCandidates.end(), greater<int>());
}
bestDown[node] = 1 + (!childCandidates.empty() ? childCandidates[0] : 0);
result = max(result, bestDown[node]);
if (childCandidates.size() >= 2) {
result = max(result, 1 + childCandidates[0] + childCandidates[1]);
}
return result;
}
int main() {
freopen("darb.in", "r", stdin);
freopen("darb.out", "w", stdout);
read();
printf("%d\n", dfs(1));
return 0;
}