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

#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;
}