Cod sursa(job #1200154)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 21 iunie 2014 23:34:01
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <vector>
#define Nmax 100005

using namespace std;

int sol,dp[Nmax];
vector <int> L[Nmax];

inline void Dfs(int nod, int tata)
{
    int max1=0,max2=0;
    vector <int>:: iterator it;
    for(it=L[nod].begin();it!=L[nod].end();++it)
        if(*it!=tata)
        {
            Dfs(*it,nod);
            if(dp[*it]>max1)
            {
                max2=max1; max1=dp[*it];
            }
            else
                if(dp[*it]>max2)
                    max2=dp[*it];
        }
    dp[nod]=max1+1;
    sol=max(sol,max1+max2+1);
}

int main()
{
    int i,x,y,N;
    freopen ("darb.in","r",stdin);
    freopen ("darb.out","w",stdout);
    scanf("%d", &N);
    for(i=1;i<N;++i)
    {
        scanf("%d%d", &x,&y);
        L[x].push_back(y);
        L[y].push_back(x);
    }
    Dfs(1,0);
    printf("%d\n", sol);
    return 0;
}