Cod sursa(job #581122)

Utilizator AndreyPAndrei Poenaru AndreyP Data 13 aprilie 2011 19:42:20
Problema Zvon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define N 100010

int n;
vector< int > g[N];
int a[N];

inline void refresh() {
	for(int i=1; i<=n; ++i)
		g[i].clear();
}

inline void citire() {
	scanf("%d",&n);

	int x,y;
	for(int i=1; i<n; ++i) {
		scanf("%d%d",&x,&y);
		g[x].pb(y);
		g[y].pb(x);
	}
}

bool compar(const int &x,const int &y) {
	return (a[x]>a[y]);
}

void dfs(int nod,int tata) {
	for(size_t i=0,lim=g[nod].size(); i<lim; ++i) {
		if(g[nod][i]==tata)
			continue;
		dfs(g[nod][i],nod);
	}

	sort(g[nod].begin(),g[nod].end(),compar);
	int t=0;
	for(int i=0,lim=g[nod].size(); i<lim; ++i) {
		if(g[nod][i]==tata)
			continue;
		++t;
		if(a[nod]<a[g[nod][i]]+t)
			a[nod] = a[g[nod][i]]+t;
	}
}

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

	int T;
	scanf("%d",&T);
	for(; T>0; --T) {
		refresh();
		citire();
		dfs(1,0);
		printf("%d\n",a[1]);
	}

	return 0;
}