Pagini recente » Cod sursa (job #90237) | Cod sursa (job #1705054) | Cod sursa (job #2576338) | Cod sursa (job #2525269) | Cod sursa (job #3196080)
#include <fstream>
#include <vector>
#define ll long long
using namespace std;
const int NMAX = 1e5;
vector <int> g[NMAX + 1];
int d[NMAX + 1];
int ans;
pair <int, int> dfs(int nod, int parent)
{
d[nod] = d[parent] + 1;
pair <int, int> dia(-1, -1);
for (int x : g[nod])
if (x != parent)
{
pair <int, int> ceva = dfs(x, nod);
if (dia.first == -1)
dia = ceva;
else
{
pair <int, int> aux;
int dist = d[dia.first] + d[ceva.first] - 2 * d[nod];
if (dist > ans)
{
ans = dist;
aux = {dia.first, ceva.first};
}
dist = d[dia.first] + d[ceva.second] - 2 * d[nod];
if (dist > ans)
{
ans = dist;
aux = {dia.first, ceva.second};
}
dist = d[dia.second] + d[ceva.first] - 2 * d[nod];
if (dist > ans)
{
ans = dist;
aux = {dia.second, ceva.first};
}
dist = d[dia.second] + d[ceva.second] - 2 * d[nod];
if (dist > ans)
{
ans = dist;
aux = {dia.second, ceva.second};
}
dia = aux;
}
}
if (dia.first == -1)
dia = {nod, nod};
return dia;
}
signed main()
{
ifstream cin("darb.in");
ofstream cout("darb.out");
int n, i;
cin >> n;
for (i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, 0);
cout << ans + 1;
}