Cod sursa(job #102541)

Utilizator GiggityGlen Quagmire Giggity Data 14 noiembrie 2007 15:05:31
Problema Zvon Scor 100
Compilator cpp Status done
Runda Happy Coding 2007 Marime 0.91 kb
#include<stdio.h>
#include<vector>
#include<algorithm>

#define NMAX 100010

using namespace std;

void df(int x);

int N, M[NMAX], seen[NMAX];
vector<int> V[NMAX], C[NMAX];

int main()
{
	int T, i, a, b;

	freopen("zvon.in", "r", stdin);
	freopen("zvon.out", "w", stdout);

	scanf("%d", &T);

	for(;T--;)
	{
		scanf("%d", &N);
		for(i = 1; i < N; i++)
		{
			scanf("%d%d", &a, &b);
			a--, b--;
			V[a].push_back(b);
			V[b].push_back(a);
		}
		
		df(0);
		printf("%d\n", M[0]);
		for(i = 0; i < N; i++)
			V[i].clear(), C[i].clear(), seen[i] = 0;
	}
	return 0;
}

void df(int x)
{
	int i;

	seen[x] = 1;

	for(i = 0; i < V[x].size(); i++)
		if(!seen[V[x][i]])
		{
			df(V[x][i]);
			C[x].push_back(M[V[x][i]]);
		}
	sort(C[x].begin(), C[x].end());

	M[x] = 0;
	for(i = 0; i < C[x].size(); i++)
		if(C[x][i] + C[x].size() - i > M[x])
			M[x] = C[x][i] + C[x].size() - i;
}