Cod sursa(job #552202)

Utilizator klamathixMihai Calancea klamathix Data 11 martie 2011 20:26:35
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<fstream>
#include<vector>
#include<algorithm>
const int maxn = 100100;
using namespace std;

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

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

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

void df(int node) {
	
	seen[node] = true;

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

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

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