Pagini recente » Cod sursa (job #3030563) | Cod sursa (job #2748409) | Cod sursa (job #2805123) | Cod sursa (job #1884950) | Cod sursa (job #2403842)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("zvon.in");
ofstream g ("zvon.out");
const int nmax=1e5+3;
int usu[nmax],t,n,x,y,nod,viz[nmax],pwp,sol[nmax];
vector <int> v[nmax];
void dfs(int nod,int ant)
{
usu[nod]=1;
for(auto i:v[nod])
{
if(i==ant) continue;
dfs(i,nod);
usu[nod]+=usu[i];
}
}
inline bool cmp(int &t1,int &t2)
{
return usu[t1]>usu[t2];
}
queue <int> q;
void bfs()
{
q.push(1);
viz[1]=1;
while(!q.empty())
{
nod=q.front();
q.pop();
for(auto i:v[nod])
{
if(viz[i]) continue;
viz[i]=1;
sol[i]=++sol[nod];
pwp=max(pwp,sol[i]);
q.push(i);
}
}
}
int main()
{
ios::sync_with_stdio(false);
f>>t;
while(t--)
{
f>>n;
for(int i=1;i<=n;++i) v[i].clear();
for(int i=1;i<n;++i)
{
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
memset(usu,0,sizeof(usu));
dfs(1,0);
for(int i=1;i<=n;++i) sort(v[i].begin(),v[i].end(),cmp);
pwp=0;
memset(sol,0,sizeof(sol));
memset(viz,0,sizeof(viz));
bfs();
g<<pwp<<'\n';
}
return 0;
}