Cod sursa(job #2769878)

Utilizator stefanvoicaVoica Stefan stefanvoica Data 18 august 2021 11:06:45
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 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;
    bool ok=0;
    for (auto y:a[x])
        if (y!=tata)
        {
            ok=1;
            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 (ok==0)
        dp[x]= {1,1};
    else
    {
        dp[x].d=max1+1;
        if (max2==INT_MIN)
            dp[x].nr=max(dp[x].nr,max1+1);
        else
        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;
}