Pagini recente » Cod sursa (job #3220897) | Cod sursa (job #2921983) | Cod sursa (job #2065014) | Cod sursa (job #1265893) | Cod sursa (job #101932)
Cod sursa(job #101932)
#include <stdio.h>
#include <fstream>
#include <vector>
#include <set>
using namespace std;
#define in "zvon.in"
#define out "zvon.out"
#define dim 100001
int T, N, M, Q;
int gasit, size=1, act_size=1, k;
int Vec[dim], list[2*dim];
bool Sel[dim], Sel2[dim];
vector< vector<int> > L, L2;
struct Functor {
bool operator() (int i, int j)
{
return Vec[i] >= Vec[j];
}
};
set<int, Functor> S;
set<int, Functor>::iterator it;
void DF(int);
void Solve(int,int);
int main()
{
int X, Y;
int maxim, poz;
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%d", &T);
for ( ; T > 0; T-- )
{
scanf("%d", &N);
memset(Sel,0,sizeof(Sel));
memset(Vec,0,sizeof(Vec));
memset(Sel2,0,sizeof(Sel2));
L.clear(); L2.clear();
L.resize(N+1); L2.resize(N+1);
if ( N == 1 )
{
printf("0\n");
continue;
}
for ( int i = 1; i < N; i++ )
scanf("%d%d", &X, &Y), L[X].push_back(Y);
DF(1);
Q = 0;
Solve(1,0);
printf("%d\n", Q);
}
}
void Solve(int nod, int timp)
{
Sel2[nod] = 1;
if ( Q < timp ) Q = timp;
// printf("%d ", nod);
for ( int i = 0; i < L[nod].size(); i++ )
{
if ( !Sel2[L[nod][i]] ) Solve(L[nod][i],timp+i+1);
}
}
void DF(int nod)
{
gasit = 0;
Sel[nod] = 1;
for ( int i = 0; i < L[nod].size(); i++ )
{
if ( !Sel[L[nod][i]] )
{
DF(L[nod][i]);
Vec[nod] += Vec[L[nod][i]] + 1;
}
}
if ( L[nod].size() == 0 ) Vec[nod] = 0;
}