Cod sursa(job #962772)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
const int Nmax=100010;
ifstream F("zvon.in");
ofstream G("zvon.out");
int T,N,D[Nmax];
vector<int> A[Nmax];
struct cmp
{
inline bool operator() (const int &a, const int &b)
{
return D[a] > D[b];
}
};
#define IT(type) vector<type>::iterator
void Get(int Nod,int Dad)
{
D[Nod]=0;
for (IT(int) it=A[Nod].begin();it!=A[Nod].end();++it)
if ( *it != Dad )
Get(*it,Nod);
if ( A[Nod].size() == 1 ) return;
sort(A[Nod].begin(),A[Nod].end(),cmp());
for (unsigned int i=0,before=1;i<A[Nod].size();++i)
if ( A[Nod][i] != Dad )
D[Nod] = max( D[ A[Nod][i] ] + int(i) + int(before), D[Nod] );
else
before = 0;
}
int main()
{
F>>T;
while ( T-- )
{
F>>N;
for (int i=1,x,y;i<N;++i)
{
F>>x>>y;
A[x].push_back(y);
A[y].push_back(x);
}
Get(1,0);
G<<D[1]<<'\n';
for(int i=1;i<=N;++i)
{
A[i].clear();
D[i] = 0;
}
}
}