Cod sursa(job #101035)

Utilizator stef2nStefan Istrate stef2n Data 12 noiembrie 2007 22:11:25
Problema Zvon Scor 100
Compilator cpp Status done
Runda Happy Coding 2007 Marime 0.88 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

#define NMAX 100005
#define pb push_back
#define sz size()

int N;
vector <int> L[NMAX];
int T[NMAX];

void read_data()
{
	int u, v;
	scanf("%d",&N);
	for(int i=1; i<=N; ++i)
		L[i].clear();
	for(int i=1; i<N; ++i)
	{
		scanf("%d %d",&u,&v);
		L[u].pb(v);
		L[v].pb(u);
	}
}

void solve(int varf, int tata)
{
	vector <int> C;
	for(int i=0; i<(int)L[varf].sz; ++i)
		if(L[varf][i]!=tata)
		{
			solve(L[varf][i],varf);
			C.pb(T[L[varf][i]]);
		}
	sort(C.begin(),C.end(),greater<int>());
	T[varf]=0;
	if(C.empty())
		return;
	for(int i=0; i<(int)C.sz; ++i)
		if(T[varf]<C[i]+(i+1))
			T[varf]=C[i]+(i+1);
}


int main()
{
	freopen("zvon.in","r",stdin);
	freopen("zvon.out","w",stdout);
	int t;
	scanf("%d",&t);
	for(; t>0; --t)
	{
		read_data();
		solve(1,-1);
		printf("%d\n",T[1]);
	}
	return 0;
}