Cod sursa(job #1461994)

Utilizator rangerChihai Mihai ranger Data 16 iulie 2015 20:18:29
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
# include <bits/stdc++.h>
using namespace std;

ifstream fi("darb.in");
ofstream fo("darb.out");

int n;
vector<int> g[100004];
int m1[100004];
int m2[100004];
int ans;
int a,b;

void dfs(int nod, int p=-1)
{
    int nr=g[nod].size();
    if (nod!=1) nr--;

    if (nr==0) return;
    if (nr==1){
        int fiu = (g[nod][0]==p ? g[nod][1] : g[nod][0]);
        dfs(fiu, nod);
        m1[nod] = m1[fiu] + 1;
        return;
    }
    for (int i=0;i<g[nod].size();i++)
    {
        if (g[nod][i]!=p)
        {
            dfs(g[nod][i],nod);
            if (m1[g[nod][i]]>m1[nod]) m2[nod]=m1[nod], m1[nod]=m1[g[nod][i]];
            else if (m1[g[nod][i]]>m2[nod]) m2[nod]=m1[g[nod][i]];
        }
    }
    m1[nod]++;
    m2[nod]++;
}

int main()
{
    fi>>n;
    for (int i=1;i<n;i++)
    {
        fi>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1);

    for (int i=1;i<=n;i++) ans = max(ans, m1[i]+m2[i]);
    fo<<ans+1;
    return 0;
}