Cod sursa(job #556882)

Utilizator bora_marianBora marian bora_marian Data 16 martie 2011 12:48:50
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<fstream>
#include<vector>
#include<set>
#define DIM 100004
using namespace std;
vector<int>G[DIM];
multiset< int >T;
int t[DIM],teste,n,best[DIM];
void solve(int k);
int maxim(int a,int b);
ofstream fout("zvon.out");
int main()
{
	ifstream fin("zvon.in");
	fin>>teste;
	int i,j;
    for(i=1;i<=teste;i++)
    {
    	fin>>n;
    	int a,b;
    	for(j=1;j<n;j++)
        {
        	t[j]=-1;
        	fin>>a>>b;
        	G[a].push_back(b);
        	G[b].push_back(a);
		}
        	t[n]=-1;
        	t[1]=0;
        	solve(1);
        	fout<<best[1]<<"\n";
        	for(j=1;j<=n;j++)
        	{
        	   G[j].erase(G[j].begin(),G[j].end());
        	   best[j]=0;
		     }
	  }
     return 0;
}
void solve(int k)
{
	int i;
	for(i=0;i<G[k].size();i++)
	   if(t[G[k][i]]==-1)
	     t[G[k][i]]=k,solve(G[k][i]);
	for(i=0;i<G[k].size();i++)
       if(G[k][i]!=t[k])	
	      T.insert(-best[G[k][i]]);
	int ord=0;
	while(T.size())
	{
		int kk=*T.begin();
		ord++;
		best[k]=maxim(best[k],-kk+ord);
		T.erase(T.begin());
	}
}           	   
int maxim(int a,int b)
{
	if(a>b)
	  return a;
	return b;
}