Cod sursa(job #3341707)

Utilizator andrei_nAndrei Nicolae andrei_n Data 20 februarie 2026 18:19:12
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("darb.in");
ofstream fout ("darb.out");

int n;
vector <int> g[100001];

int dist1[100001];
void dfs1(int node, int parent)
{
    for (auto vecin : g[node])
        if (vecin != parent)
        {
            dist1[vecin] = dist1[node] + 1;
            dfs1(vecin, node);
        }
}

int dist2[100001];
void dfs2(int node, int parent)
{
    for (auto vecin : g[node])
        if (vecin != parent)
        {
            dist2[vecin] = dist2[node] + 1;
            dfs2(vecin, node);
        }
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dist1[1] = 0;
    dfs1(1, 0);

    int dmax = 0, farthest;
    for (int node = 1; node <= n; node++)
        if (dist1[node] > dmax)
        {
            dmax = dist1[node];
            farthest = node;
        }

    dfs2(farthest, 0);
    dmax = 0;
    for (int node = 1; node <= n; node++)
        if (dist2[node] > dmax)
        {
            dmax = dist2[node];
            farthest = node;
        }
    fout << dmax + 1;
    return 0;
}