Cod sursa(job #1650466)

Utilizator george_stelianChichirim George george_stelian Data 11 martie 2016 18:33:19
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <vector>

using namespace std;

vector<int> v[100010];
int d[100010][2],sol;

void dfs(int nod,int tata)
{
    for(vector<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
        if(*it!=tata)
        {
            dfs(*it,nod);
            if(d[*it][0]>d[nod][0]) {d[nod][1]=d[nod][0];d[nod][0]=d[*it][0];}
            else if(d[*it][0]>d[nod][1]) d[nod][1]=d[*it][0];
        }
    d[nod][0]++;
    sol=max(sol,d[nod][0]+d[nod][1]);
}

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