Cod sursa(job #552184)

Utilizator lalasCont de teste lalas Data 11 martie 2011 20:05:22
Problema Zvon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<fstream>
#include<vector>
#include<algorithm>
const int maxn = 100005;
using namespace std;

ifstream fin("zvon.in");
ofstream fout("zvon.out");

int i , j , a , b, dp[maxn] , sum[maxn] , n , t;
bool seen[maxn];
vector <int> G[maxn];

bool cmp (int i, int j) {
	return sum[i] > sum[j];
}

void df(int node) {
	
	seen[node] = true;
	sum[node] = 1;
	
	int i;
	for( i = 0 ; i < G[node].size() ; ++i )
		if ( ! seen[G[node][i]] ) {
			int act = G[node][i];
			df(act);
			sum[node] += sum[act];
		}
		
	sort( G[node].begin() , G[node].end() , cmp );
	
	for( i = 0 ; i < G[node].size() - 1; ++i ) 
		dp[node] = max(dp[node] , dp[G[node][i]] + i + 1);
}

void clear() 
{
	int i;
	for( i = 1 ; i <= n ; ++i ) 
		G[i].clear() , seen[i] = false ,
		dp[i] = 0;
}

int main()
{
	for( fin >> t; t -- ; ) {		
		fin >> n;
		for( i = 1 ; i < n ; ++i ) {
			fin >> a >> b , 
			G[a].push_back(b),
			G[b].push_back(a);
		}
		
		df(1);
		fout << dp[1] << "\n";
		clear();
	}
	
return 0;
}