Problem link We find an odd nodes tree has only one centroid. So if $$$n$$$ is odd, we don't change it. If $$$n$$$ is even, we delete an leaf and make it odd. Then we insert the deleted leaf to the centroid. And sorry for I met many bugs. Hope you can't meet them. Becareful. 1st Wrong Answer Okay, we need max to be min. 2nd Wrong Answer No, we just calculated the deleted leaf in!!! 3rd Wrong Answer It's not finished though. The nodes after delete is $$$n-1$$$ not $$$n$$$. AC link cpp #include <bits/stdc++.h> #define N 100005 using namespace std; int T,n; vector<int> g[N]; int s[N],mx[N],C,Leaf; int leaf(int x,int fa){//O(depth) find a leaf if(g[x].size()==1&&fa)return x;//Not the root so fa!=0 for(int y:g[x]){ if(y==fa)continue; return leaf(y,x); } } void dfs(int x,int fa){//Calculate all subtree node numbers s[x]=1;mx[x]=0;//Init for(int y:g[x]){ if(y==fa||y==Leaf)continue; dfs(y,x);//Calculate the subtree mx[x]=max(mx[x],s[y]); s[x]+=s[y]; } mx[x]=max(mx[x],n-1-s[x]);//Caution: As x is the root, then the origin father is follow x's subtree. So we have another subtree with its father and uncles. // (1) // / \ // (x) (3) // | // (2) //Like up graph and at X we have subtree (2) and also (1)-(3). } void solve(){ cin>>n; for(int i=1;i<=n;i++)g[i].clear();//clear the graph for(int i=1,u,v;i<n;i++){//input the graph cin>>u>>v; g[u].push_back(v),g[v].push_back(u); } if(n&1){//N is odd and the tree can only have one centroid. Just randomly delete an edge and add it back. cout<<1<<" "<<g[1][0]<<"\n"; cout<<1<<" "<<g[1][0]<<"\n"; return; } //Now N is even. We need delete an edge and connect it with our Subtree's centroid. Leaf=leaf(1,0); cout<<Leaf<<" "<<g[Leaf][0]<<"\n"; C=0;mx[C]=0x3f3f3f3f; dfs(1,0); //Now we find the centroid. for(int i=1;i<=n;i++){ if(i==Leaf)continue; if(mx[i]<mx[C]){ //cout<<i<<" is better:"<<mx[i]<<'\n'; C=i; } } //Now centroid is C. cout<<Leaf<<" "<<C<<'\n'; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//Make input faster cin>>T;while(T--)solve(); return 0; }