Pagini recente » Istoria paginii monthly-2014/runda-3/clasament | Cod sursa (job #2489247) | Cod sursa (job #2077075) | Cod sursa (job #2986498) | Cod sursa (job #124150)
Cod sursa(job #124150)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 1024*128
long first[maxn];
long v[maxn*2],next[maxn*2];
long sel[maxn];
long val[maxn];
long fii[maxn];
long n;
int cmpint(const void *a, const void *b)
{
return -( *(long *) a - * ( long *) b);
}
long rez(long a)
{
sel[a] = -1;
val[a] = 0;
long x = first[a];
while( x)
{
if( sel[v[x]] == 0)
rez(v[x]);
x = next[x];
}
x = first[a];
long t = 0;
while(x)
{
if( sel[v[x]] == 1)
fii[++t] = val[v[x]];
x = next[x];
}
qsort(fii+1,t,sizeof(fii[1]),cmpint);
sel[a] = 1;
for(long i = 1; i <= t; i++)
if( fii[i] + i > val[a])
val[a] = fii[i] + i;
return val[a];
}
int main()
{
freopen("zvon.in","r",stdin);
freopen("zvon.out","w",stdout);
long nr_caz,a,b;
scanf("%ld",&nr_caz);
for( long ii = 1; ii <= nr_caz; ++ii)
{
scanf("%ld",&n);
memset(first,0,sizeof(first));
memset(sel,0,sizeof(first));
for( long i = 1; i < n; ++i)
{
scanf("%ld %ld",&a,&b);
v[i*2 - 1] = a;
v[i*2] = b;
next[i*2] = first[a];
next[i*2-1] = first[b];
first[a] = i *2;
first[b] = i *2-1;
}
printf("%ld\n",rez(1));
}
return 0 ;
}