Pagini recente » Cod sursa (job #817039) | Rating Vlad Corjuc (vladcorjuc) | Cod sursa (job #1256233) | Cod sursa (job #1143340) | Cod sursa (job #644890)
Cod sursa(job #644890)
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
#define maxim(a,b) (a>b ? a : b)
#define pb push_back
#define NMAX 100005
vector<int> v[NMAX];
char viz[NMAX];
int t,n,m;
int tata[NMAX];
int sol[NMAX];
int vect[NMAX];
void dfs(int nod)
{
int i,nr,vec,lim=v[nod].size();
viz[nod]=1;
for(i=0;i<lim;i++)
if(!viz[vec=v[nod][i]])
dfs(vec);
else
tata[nod]=vec;
nr=0;
for(i=0;i<lim;i++)
if(v[nod][i]!=tata[nod])
vect[++nr]=sol[v[nod][i]];
sort(vect+1,vect+nr+1);
for(i=nr;i>=1;i--)
sol[nod]=maxim(sol[nod],nr-i+1+vect[i]);
}
int main ()
{
int i,a,b;
freopen("zvon.in","r",stdin);
freopen("zvon.out","w",stdout);
scanf("%d",&t);
for(;t;t--)
{
scanf("%d",&n);
for(i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
v[a].pb(b);
v[b].pb(a);
}
memset(viz,0,sizeof(viz));
memset(sol,0,sizeof(sol));
dfs(1);
printf("%d\n",sol[1]);
for(i=1;i<=n;i++)
v[i].clear();
}
return 0;
}