Pagini recente » Cod sursa (job #324025) | Cod sursa (job #2614670) | Cod sursa (job #1622604) | Cod sursa (job #3206485) | Cod sursa (job #1919281)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
vector< vector<int> >g(100010);
int depth[100010];
int timp[100010];
bool viz[100010];
int maxi;
bool cmp(int x,int y)
{
return depth[x]<depth[y];
}
int maxim(int a,int b)
{
if(a>b)
return a;
else
return b;
}
void dfs(int node)
{
int i,l,maxi1;
viz[node]=true;
maxi1=0;
l=g[node].size();
for(i=0;i<l;i++)
{
if(viz[g[node][i]]==false)
{
dfs(g[node][i]);
maxi1=maxim(maxi1,depth[g[node][i]]);
}
}
depth[node]=maxi1+1;
}
void ans(int node)
{
int i,l;
viz[node]=true;
maxi=maxim(maxi,timp[node]);
l=g[node].size();
for(i=l-1;i>=0;i--)
{
if(viz[g[node][i]]==false)
{
timp[g[node][i]]=timp[node]+l-i;
ans(g[node][i]);
}
g[node].pop_back();
}
}
void solve()
{
memset(viz,0,sizeof(viz));
memset(depth,0,sizeof(depth));
memset(timp,0,sizeof(timp));
maxi=0;
int n,i,x,y;
scanf("%d",&n);
for(i=1;i<=n-1;i++)
{
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1);
for(i=2;i<=n;i++)
{
sort(g[i].begin(),g[i].end(),cmp);
g[i].pop_back();
}
sort(g[1].begin(),g[1].end(),cmp);
memset(viz,0,sizeof(viz));
ans(1);
printf("%d\n",maxi);
}
int main()
{
freopen("zvon.in","r",stdin);
freopen("zvon.out","w",stdout);
int t,i;
scanf("%d",&t);
for(i=1;i<=t;i++)
solve();
return 0;
}