Cod sursa(job #193597)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 5 iunie 2008 09:11:46
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#define N 131075
long f[N],v[N*2],next[N*2],s[N],v2[N],f2[N],n;
int qfunct(const void *a,const void *b){
	return -(*(long *)a-*(long *)b);
}
long rez(long a){
	s[a]=-1;
	v2[a]=0;
	long x=f[a],t=0,i;
	while(x){
		if(s[v[x]]==0){
			rez(v[x]);
		}
		x=next[x];
	}
	x=f[a];
	while(x){
		if(s[v[x]]==1){
			f2[++t]=v2[v[x]];
		}
		x=next[x];
	}
	qsort(f2+1,t,sizeof(f2[1]),qfunct);
	s[a]=1;
	for(i=1;i<=t;++i){
		if(f2[i]+i>v2[a]){
			v2[a]=f2[i]+i;
		}
	}
	return v2[a];
}
int main(){
	long nr,a,b,i,j;	
	freopen("zvon.in","r",stdin);
	freopen("zvon.out","w",stdout);
	scanf("%ld",&nr);
	for(j=1;j<=nr;++j){
		scanf("%ld",&n);
		memset(f,0,sizeof(f));
		memset(s,0,sizeof(f));
		for(i=1;i<n;++i){
			scanf("%ld %ld",&a,&b);
			v[i*2-1]=a;
			v[i*2]=b;
			next[i*2]=f[a];
			next[i*2-1]=f[b];
			f[a]=i*2;
			f[b]=i*2-1;
		}
		printf("%ld\n",rez(1));
	}
	return 0;
}