Cod sursa(job #1565287)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 10 ianuarie 2016 16:37:59
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>
#define Nmax 100005
#define pb push_back

using namespace std;

int n,dp[Nmax],v[Nmax];
vector <int> L[Nmax];

inline void Dfs(int nod, int tata)
{
    for(auto it : L[nod])
    {
        if(it==tata) continue;
        Dfs(it,nod);
    }
    int l=0;
    for(auto it : L[nod])
    {
        if(it==tata) continue;
        v[++l]=dp[it];
    }
    if(!l) return;
    sort(v+1,v+l+1);
    for(int i=1;i<=l;++i) dp[nod]=max(dp[nod],v[i]+l-i+1);
}

int main()
{
    int T,x,y,i;
    ifstream cin("zvon.in");
    ofstream cout("zvon.out");
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(i=1;i<=n;++i)
        {
            L[i].clear(); dp[i]=0;
        }
        for(i=1;i<n;++i)
        {
            cin>>x>>y;
            L[x].pb(y); L[y].pb(x);
        }
        Dfs(1,0);
        cout<<dp[1]<<"\n";
    }
    return 0;
}