Cod sursa(job #2769876)

Utilizator stefanvoicaVoica Stefan stefanvoica Data 18 august 2021 11:02:12
Problema Diametrul unui arbore Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define dim 100002
#define int long long
using namespace std;
ifstream fin ("darb.in");
ofstream fout("darb.out");
const int inf=100000000000000;
vector<int> a[dim];

struct el
{
    int d,nr;
} dp[dim];

void dfs (int x,int tata)
{
    int max1=INT_MIN,max2=INT_MIN;
    for (auto y:a[x])
        if (y!=tata)
        {
            dfs(y,x);
            if (dp[y].d>max1)
            {
                max2=max1;
                max1=dp[y].d;
            }
            else    if (dp[y].d>max2)
                max2=dp[y].d;
            dp[x].nr=max(dp[x].nr,dp[y].nr+1);
        }
    if (a[x].size()==1)
        dp[x]= {1,1};
    else
    {
        dp[x].d=max1+1;
        dp[x].nr=max(dp[x].nr,max1+max2+1);
    }
}

void Solve ()
{
    int i,n,x,y,maxi=0;
    fin>>n;
    for (i=1; i<n; i++)
    {
        fin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1,0);
    for (i=1; i<=n; i++)
        maxi=max(maxi,dp[i].nr);
    fout<<maxi<<'\n';
}

int32_t main()
{
    int t=1;
    //  fin>>t;
    while (t--)
    {
        Solve();
    }
    return 0;
}