Cod sursa(job #108255)

Utilizator VmanDuta Vlad Vman Data 21 noiembrie 2007 22:48:40
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
using namespace std;
#include <stdio.h>
#include <vector>
#include <algorithm>

#define Nmax 100001

int T,N,i,x,y;
vector<int> f[Nmax];

inline int maxim(int a,int b) { return a>b?a:b; }

int dfs(int nod)
{
 vector<int> delay;
 vector<int>::iterator it;
 int i,k,min;
 for (it=f[nod].begin();it<f[nod].end();++it)
      delay.push_back(dfs(*it));
 sort(delay.begin(),delay.end());
 k=delay.size();
 min=0;
 for (i=0;i<k;++i)
     min=maxim(delay[i]+k-i,min);
 return min;
}

int main()
{
 freopen("zvon.in","r",stdin);
 freopen("zvon.out","w",stdout);
 scanf("%d",&T);
 while (T>0)
       {
        --T;
        scanf("%d",&N);
        for (i=1;i<N;++i)
            {
             scanf("%d %d",&x,&y);
             f[x].push_back(y);
            }
        printf("%d\n",dfs(1));
       for (i=1;i<=N;++i)
          f[i].clear();
                 }
 fclose(stdin);
 fclose(stdout);
 return 0;
}