Cod sursa(job #96795)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 3 noiembrie 2007 15:24:29
Problema Zvon Scor Ascuns
Compilator cpp Status done
Runda Marime 0.84 kb
#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;
}