Pagini recente » Cod sursa (job #2036834) | Cod sursa (job #1069251) | Cod sursa (job #2468356) | Cod sursa (job #1683304) | Cod sursa (job #1919574)
#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)
{
if(depth[x]<=depth[y])
return 1;
else
return 0;
}
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]);
}
}
}
int main()
{
freopen("zvon.in","r",stdin);
freopen("zvon.out","w",stdout);
int t,n,i,x,y,j;
scanf("%d",&t);
for(j=1; j<=t; j++)
{
/* memset(viz,0,sizeof(viz));
memset(depth,0,sizeof(depth));
memset(timp,0,sizeof(timp));*/
maxi=0;
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();
viz[i]=false;
}
sort(g[1].begin(),g[1].end(),cmp);
//memset(viz,0,sizeof(viz));
ans(1);
printf("%d\n",maxi);
for(i=1; i<=n; i++)
{
depth[i]=0;
timp[i]=0;
viz[i]=false;
g[i].clear();
}
}
return 0;
}