1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
vector<int>e[222222],zj;
int pre[222222],dep[222222];
int pos,st,ed;
int n;
int vis[222222],tot[222222];
int in[222222];
deque<pii>q;
void dfs(int u,int f)
{
pre[u]=f,pos=(dep[pos]<dep[u])?u:pos;
for(int v:e[u]) if(v^f) dep[v]=dep[u]+1,dfs(v,u);
}
void dfs2(int u,int f)
{
//printf("u:%lld\n",u);
if(in[u]==1) q.pb(mkp(u,0));
for(int v:e[u]) if(v^f) dfs2(v,u);
}
pii bfs(int u,int f)
{
//test
//printf("ASD:%lld",in[u]);
if(!in[u]) return mkp(u,0);
//test
dfs2(u,f);
pii ret;
memset(tot,0,sizeof(tot));
while((int)q.size()>0)
{
auto qwq=q.front();q.pop_front();
//printf("qwq:%lld\n",qwq.fi);
ret=qwq;
tot[ret.se]++;
for(int v:e[qwq.fi]) if(v^f&&in[v]^1)
{
in[v]--;
if(in[v]==1) q.pb(mkp(v,ret.se+1));
}
}
ret.se+=(tot[ret.se]>1);
return ret;
}
signed main()
{
for(int _=read();_;_--)
{
n=read();memset(in,0,sizeof(in));
R(i,0,n+1) e[i].clear();zj.clear(),dep[pos=0]=0;
int u,v;R(i,2,n) u=read(),v=read(),e[u].pb(v),e[v].pb(u),in[u]++,in[v]++;
dfs(1,-1);st=pos;dep[st]=0;
dfs(st,-1);ed=pos;
for(int cur=ed;~cur;cur=pre[cur]) zj.pb(cur);int len=(int)zj.size();
int uuu=zj[len/2],vvv=zj[len/2-1];in[uuu]--,in[vvv]--;
//printf("???:%lld %lld\n",uuu,vvv);
//printf("asd:%lld %lld\n",in[uuu],in[vvv]);
pii r1=bfs(uuu,vvv);
//puts("2:");
pii r2=bfs(vvv,uuu);
printf("%lld %lld %lld\n",max(r1.se,r2.se),r1.fi,r2.fi);
}
}
|