Cod sursa(job #1435412)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 13 mai 2015 00:33:28
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;

#define NMAX 100001

vector <int> v[NMAX];
int viz[NMAX],d[NMAX];

void dfs(int nod)
{
	int nr,maxim,i;
	viz[nod]=1;
	nr=0;
	for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++) 
		if(viz[*it]==0)
			nr++;
	int *x = new int[nr+1];
	nr=0;
	for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++) 
		if(viz[*it]==0) {
			dfs(*it);
			x[++nr]=d[*it];
		}
	maxim=0;
	sort(x+1,x+nr+1,std::greater<int>());
	for(i=1;i<=nr;i++)
		maxim=max(maxim,i+x[i]);
	free(x);
	d[nod]=maxim;
}

int main ()
{
	int n,t,i,x,y;
	ifstream f("zvon.in");
	ofstream g("zvon.out");
	f>>t;
	while(t--) {
		f>>n;
		for(i=1;i<=n-1;i++) {
			f>>x>>y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		memset(viz,0,sizeof(viz));
		memset(d,0,sizeof(d));
		dfs(1);
		g<<d[1]<<'\n';
		for(i=1;i<=n;i++)
			v[i].clear();
	}
	f.close();
	g.close();
	return 0;
}