Cod sursa(job #556509)

Utilizator bora_marianBora marian bora_marian Data 16 martie 2011 10:20:27
Problema Zvon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<fstream>
#include<vector>
#include<queue>
#include<set>
#define DIM 100004
using namespace std;
int adan[DIM],cop[DIM],maxim,viz[DIM],n,sol,rez;
int T,t[DIM];
vector<int>G[DIM];
queue<int>S;
set< pair<int,int > >SE;
void DF(int k);
void solve();
int main()
{
	ifstream fin("zvon.in");
	ofstream fout("zvon.out");
	fin>>T;
	int i,j;
	for(i=1;i<=T;i++)
	{
		fin>>n;
		int a,b;
		rez=0;
		viz[n]=0;
		adan[n]=0;
		cop[n]=0;
		for(j=1;j<n;j++)
		{
		   viz[j]=0;
		   adan[j]=0;
		   cop[j]=0;
		   fin>>a>>b;
		   G[a].push_back(b);
		   G[b].push_back(a);
	    }
	    if(n>1)
	    {
	    DF(1);
	    solve();
	    for(j=1;j<=n;j++)
	       rez=max(rez,adan[j]);   
	    for(j=1;j<=n;j++)
	    {
	    	G[j].erase(G[j].begin(),G[j].end()); 
		}
	    } 	     
	    fout<<rez<<"\n";
	 }
	 return 0;
 }
void DF(int k)
{
	viz[k]=1;
	for(int i=0;i<G[k].size();i++)        
       if(viz[G[k][i]]==0)
          t[G[k][i]]=k,DF(G[k][i]);
    cop[t[k]]+=cop[k]+1;
}
void solve()
{
	int i;
	for(i=1;i<=n;i++)
	   viz[i]=0;
	S.push(1);
	while(S.size()>0)
	{   
       int k=S.front();
       viz[k]=1;
       for(i=0;i<G[k][i];i++)
          if(viz[G[k][i]]==0)
            SE.insert(make_pair(-cop[G[k][i]],G[k][i]));
       int ord=0;
       while(SE.size()>0)
       {
       	  int kk=(*SE.begin()).second;
       	  ord++;
       	  adan[kk]=adan[t[kk]]+ord;
       	  S.push(kk);
       	  SE.erase(SE.begin());
	   }
	   S.pop();
     }
}