Pagini recente » Cod sursa (job #1129606) | Cod sursa (job #2609205) | Cod sursa (job #2281023) | Cod sursa (job #1820390) | Cod sursa (job #193597)
Cod sursa(job #193597)
#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;
}