Pagini recente » Cod sursa (job #1100935) | Cod sursa (job #797720) | Cod sursa (job #2088652) | Cod sursa (job #1280709) | Cod sursa (job #1911316)
#include <bits/stdc++.h>
using namespace std;
const int nMax = 1e5 + 2;
int n, dp[nMax][2];
vector<int>g[nMax];
void add_edge(int a, int b) {
g[a].push_back(b);
g[b].push_back(a);
}
void upd(pair<int, int>&that, int value) {
if (value > that.first) {
that.second = that.first;
that.first = value;
}
else if (value > that.second) {
that.second = value;
}
}
int diam(int nod, int tata) {
int res = 0;
dp[nod][0] = 1;
pair<int, int>best(0, 0);
for (const auto& fiu : g[nod]) {
if (fiu == tata)
continue;
res = max(res, diam(fiu, nod));
upd(best, dp[fiu][0]);
dp[nod][0] = max(dp[nod][0], dp[fiu][0] + 1);
}
dp[nod][1] = best.first + best.second + 1;
res = max(res, dp[nod][0]);
res = max(res, dp[nod][1]);
return res;
}
int main() {
ifstream cin("darb.in");
ofstream cout("darb.out");
cin >> n;
for (int i = 1; i < n; ++i) {
int x, y;
cin >> x >> y;
add_edge(x, y);
}
cout << diam(1, 0);
return 0;
}