Cod sursa(job #3213277)

Utilizator QwertyDvorakQwerty Dvorak QwertyDvorak Data 12 martie 2024 20:24:12
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define dbg(x) cout << #x << ": " << x << "\n";
using ll = long long;

const string myf = "darb";
ifstream fin(myf + ".in");
ofstream fout(myf + ".out");

int n, x, y, ans;
int dp[100005];
vector<int> g[100005];

void dfs(int x, int last)
{
    int max1, max2;
    max1 = max2 = 0;
    for (auto i : g[x])
        if (i != last)
        {
            dfs(i, x);
            if (max1 < dp[i])
                max2 = max1, max1 = dp[i];
            else if (max2 < dp[i])
                max2 = dp[i];
        }
    dp[x] = max1 + 1;
    ans = max(ans, max1 + max2 + 1);
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
    {
        fin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1, 0);
    fout << ans << '\n';

    fin.close();
    fout.close();
    return 0;
}