Cod sursa(job #2116906)

Utilizator patcasrarespatcas rares danut patcasrares Data 28 ianuarie 2018 12:16:45
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<fstream>
#include<iostream>
#include<vector>
#define DN 100005
#define pb push_back
using namespace std;
ifstream fin("amici2.in");
ofstream fout("amici2.out");
int t,n,m,dp[DN],p,q,viz[DN],pr[DN],f,dp2[DN],ma;
vector<int>v[DN];
void dfs(int nod)
{
    viz[nod]=1;
    int ma1=0,ma2=0;
    for(auto i:v[nod])
        if(viz[i]==0)
        {
            dp2[i]=1;
            dfs(i);
            dp2[nod]=max(dp2[nod],dp2[i]+1);
            if(dp2[i]>ma1)
            {
                ma2=ma1;
                ma1=dp2[i];
            }
            else
                if(dp2[i]>ma2)
                    ma2=dp2[i];
        }
    dp[nod]=ma1+ma2+1;
}
int main()
{
    t=1;
    for(int h=1;h<=t;h++)
    {
        fin>>n;
        m=n-1;
        for(int i=1;i<=n;i++)
        {
            viz[i]=dp[i]=dp2[i]=0;
            v[i].clear();
        }
        for(int i=1;i<=m;i++)
        {
            fin>>p>>q;
            v[p].pb(q);
            v[q].pb(p);
        }
        dp2[1]=1;
        dfs(1);
        for(int i=1;i<=n;i++)
            ma=max(ma,dp[i]);
        fout<<ma<<'\n';
    }
}