Pagini recente » Cod sursa (job #377361) | Cod sursa (job #2885035) | Cod sursa (job #427677) | Cod sursa (job #2208686) | Cod sursa (job #107672)
Cod sursa(job #107672)
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define sz size()
#define nmax 100111
int n,T,A[nmax],H[nmax];
vector <int> G[nmax];
void doit(int i,int p)
{
int j;
FOR(j,0,G[i].sz)
if(G[i][j]!=p)
doit(G[i][j],i);
FOR(j,0,G[i].sz)
if(G[i][j]!=p)
H[j]=A[G[i][j]];
else
H[j]=nmax;
A[i]=0;
if(G[i].sz)
{
sort(H,H+G[i].sz);
reverse(H,H+G[i].sz-1);
FOR(j,0,G[i].sz-1)
if(H[j]+j>=A[i])
A[i]=H[j]+j+1;
}
}
int main()
{
int i,j,ii,iii;
freopen("zvon.in","r",stdin);
freopen("zvon.out","w",stdout);
scanf("%d",&T);
FOR(ii,0,T)
{
scanf("%d",&n);
FOR(i,0,n)
G[i].clear();
FOR(iii,1,n)
{
scanf("%d %d",&i,&j);i--,j--;
G[i].pb(j); G[j].pb(i);
}
G[0].pb(-1);
doit(0,-1);
printf("%d\n",A[0]);
}
return 0;
}