Cod sursa(job #100795)

Utilizator devilkindSavin Tiberiu devilkind Data 12 noiembrie 2007 19:00:16
Problema Zvon Scor 100
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.33 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 100002
#define pb push_back

long int a[NMAX],i,j,k,n,m,x,y,h[NMAX];

vector<int> G[NMAX];

void init()
{
for (i=0;i<=n;i++)
        G[i].clear();

memset(h,0,sizeof(h));
}

int cmp(long int x, long int y)
{
return (x>y);
}

inline long int MAXX(long int a, long int b)
{
if (a<b) return b;
return a;
}

void DF(long int nod)
{

h[nod]=1;

long int i,k;
vector<int> v;

for (i=0;i<G[nod].size();i++)
        if (!h[G[nod][i]]) {
                           DF(G[nod][i]);
                           v.pb(a[G[nod][i]]);
                           }

sort(v.begin(),v.end(),cmp);

k=v.size()-1;
a[nod]=0;

for (i=0;i<=k;i++)
         a[nod]=MAXX(v[i]+i+1,a[nod]);
}

int main()
{
        freopen("zvon.in","r",stdin);
        freopen("zvon.out","w",stdout);

        long int nrt,T;

        scanf("%ld",&T);

        for (nrt=1;nrt<=T;nrt++)
                {

                scanf("%ld",&n);

                init();

                for (i=1;i<=n-1;i++)
                        {
                        scanf("%ld %ld",&x,&y);

                        G[x].pb(y);
                        G[y].pb(x);                        
                        }

                DF(1);

                printf("%ld\n",a[1]);
                }
        return 0;
}