Cod sursa(job #99473)

Utilizator alextheroTandrau Alexandru alexthero Data 11 noiembrie 2007 11:49:01
Problema Zvon Scor 100
Compilator cpp Status done
Runda Happy Coding 2007 Marime 0.87 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>

#define nmax 100005
#define pb push_back

using namespace std;

int T, n, x1, y1, a[nmax];
vector <int> e[nmax];
char v[nmax], s[20];

void dfs(int x)
{
	vector <int> v1;
	v[x] = 1;
	for(int i = 0; i < (int)e[x].size(); i++)
		if(!v[e[x][i]])
		{
			dfs(e[x][i]);
			v1.pb(a[e[x][i]]);
		}
	sort(v1.begin(), v1.end());
	reverse(v1.begin(), v1.end());
	a[x] = 0;
	for(int i = 0; i < (int)v1.size(); i++) 
		a[x] = max(a[x], v1[i] + i + 1);
}

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

	scanf("%d", &T);
	for(int t = 1; t <= T; t++)
	{
		scanf("%d", &n);
		for(int i = 1; i <= n; i++) e[i].clear();
		for(int i = 1; i < n; i++)
		{
			scanf("%d%d", &x1, &y1);
			e[x1].pb(y1);
			e[y1].pb(x1);
		}
		memset(v, 0, sizeof(v));
		dfs(1);
		printf("%d\n", a[1]);
	}

	return 0;
}