Pagini recente » Cod sursa (job #148709) | Cod sursa (job #253626) | Cod sursa (job #3216884) | Cod sursa (job #1980125) | Cod sursa (job #107608)
Cod sursa(job #107608)
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define pb push_back
#define vi vector<int>
#define vii vector<int> :: iterator
const int maxn = 100100;
int nrt,i,n,din[maxn];
vi vects;
vi vect[maxn];
int ver[maxn];
int s;
int j,x,y;
int max(int i,int j)
{
return i > j ? i : j;
}
bool cmpf(const int i,const int j)
{
return i > j;
}
void dfs(int i)
{
vii it;
for(it = vect[i].begin(); it != vect[i].end(); ++it)
{
if (!ver[*it])
{
ver[*it] = i;
dfs(*it);
}
}
for(it = vect[i].begin(); it != vect[i].end(); ++it)
{
if (ver[i] != *it)
{
vects.pb(din[*it]);
++s;
}
}
sort(vects.begin(),vects.end(),cmpf);
for(j = 0;j < s; ++j)
{
din[i] = max(din[i],vects[j] + j + 1);
}
vects.clear();
s = 0;
}
int main()
{
freopen("zvon.in","r",stdin);
freopen("zvon.out","w",stdout);
scanf("%d",&nrt);
for(;nrt;--nrt)
{
scanf("%d",&n);
for(i = 1;i < n; ++i)
{
scanf("%d %d",&x,&y);
vect[x].pb(y);
vect[y].pb(x);
}
ver[1] = 1;
dfs(1);
printf("%d\n",din[1]);
for(i = 1;i <= n; ++i)
{
ver[i] = 0;
vect[i].clear();
din[i] = 0;
}
}
return 0;
}