Pagini recente » Cod sursa (job #2292913) | Cod sursa (job #1335084) | Cod sursa (job #2054808) | Cod sursa (job #233517) | Cod sursa (job #556509)
Cod sursa(job #556509)
#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();
}
}