Cod sursa(job #106604)

Utilizator tvladTataranu Vlad tvlad Data 18 noiembrie 2007 19:43:26
Problema Zvon Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 0.76 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 100000;

int n;
int d[N];
vector<int> v[N];

void df ( int x ) {
	vector<int> t;
	for (int i = 0; i < v[x].size(); ++i) {
		df(v[x][i]);
		t.push_back(d[v[x][i]]);
	}
	sort(t.begin(),t.end());
	if (t.size()>0) {
		d[x] = t[t.size()-1]+1;
		for (int i = 0; i < t.size(); ++i) {
			d[x] = max(d[x],t[i]+t.size()-i);
		}
	}
}

int main() {
	freopen("zvon.in","rt",stdin);
	freopen("zvon.out","wt",stdout);
	int t;
	for (scanf("%d",&t); t > 0; --t) {
		scanf("%d",&n);
		for (int i = 0; i<N; ++i) {
			v[i].clear();
			d[i] = 0;
		}
		for (int i = 0; i < n-1; ++i) {
			int a,b;
			scanf("%d %d",&a,&b);
			--a; --b;
			v[a].push_back(b);
		}
		df(0);
		printf("%d\n",max);
	}
	return 0;
}