Cod sursa(job #107175)

Utilizator CezarMocanCezar Mocan CezarMocan Data 19 noiembrie 2007 14:04:03
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <algorithm>

using namespace std;

long n,i,j,k,tt,ind[100100],id[100100],t[100100],nr[100100],x[100100],y[100100],v[100100];

void df(int nod)
{
int i,aux;
for (i=ind[nod]+1;i<=ind[nod+1];i++)
      df(v[i]);
nr[0]=0;
for (i=ind[nod]+1;i<=ind[nod+1];i++)
    {
    nr[0]++;
    nr[nr[0]]=t[v[i]];    
    }
sort(nr+1,nr+nr[0]+1);
for (i=1;i<=nr[0]/2;i++)
    {
    aux=nr[i];
    nr[i]=nr[nr[0]-i+1];
    nr[nr[0]-i+1]=aux;    
    }
for (i=1;i<=nr[0];i++)
    {
    if (nr[i]+i>t[nod])
        t[nod]=nr[i]+i;    
    }
}

int main(){
freopen("zvon.in","r",stdin);
freopen("zvon.out","w",stdout);
scanf("%d",&tt);
for (k=1;k<=tt;k++)
    {
    scanf("%d",&n);    
    for (i=2;i<=n;i++)
        {
        scanf("%d %d",&x[i],&y[i]);    
        ind[x[i]]++;
        }
    for (i=2;i<=n;i++)
        ind[i]+=ind[i-1];
    for (i=n;i>=1;i--)
        ind[i]=ind[i-1];
    for (i=2;i<=n;i++)
        {
        id[x[i]]++;   
        v[ind[x[i]]+id[x[i]]]=y[i];
        }
    ind[n+1]=ind[n]+id[n];
    df(1);
    printf("%d\n",t[1]);
    for (i=0;i<=100000;i++)
        {
        v[i]=0;
        ind[i]=0;
        id[i]=0;
        nr[i]=0;
        t[i]=0;
        }
    }
return 0;   
}