Pagini recente » Cod sursa (job #2587469) | Cod sursa (job #316270) | Cod sursa (job #535308) | Cod sursa (job #2171000) | Cod sursa (job #556882)
Cod sursa(job #556882)
#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;
}