Cod sursa(job #124150)

Utilizator marius135Dumitran Adrian Marius marius135 Data 18 ianuarie 2008 13:04:15
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#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 ;
}