C. Link Cut Centroids

图片说明
图片说明
图片说明

思路

把一个重心下的子树上的一个叶子节点，移动到另一个重点作为孩子节点即可

代码

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e6+10;
const ll maxM = 1e6+10;
const ll inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

template<class T> void pt(T x){
    cout<<x<<" ";
}

template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout<<t<<" ";
    pt(data...);
}


//--------------------------------------------

int T,N;
int h[maxn],e[maxn],ne[maxn],idx = 1;
int sz[maxn];
void add(int a,int b){
    e[++idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
}
int H1,H2,mx = inf;
int yz,yzfa;
void dfs(int u,int fa){
    sz[u] = 1;
    int curmx = 0;
    for(int i = h[u];i; i = ne[i]){
        int v = e[i];
        if(v == fa) continue;
        dfs(v,u);
        sz[u] += sz[v];
        curmx = max(curmx,sz[v]);
    }
    curmx = max(curmx,N-sz[u]);
    if(curmx < mx){
        mx = curmx;
        H1 = u;
        H2 = -1;
    }else if(curmx == mx){
        H2 = u;
    }
}
void dfs2(int u,int fa){
    int yy = 1;
    for(int i = h[u];i;i = ne[i]){
        int v = e[i];
        if(v == fa || v == H2) continue;
        yy = 0;
        dfs2(v,u);
    }
    if(yy){
        yz = u;
        yzfa = fa;
    }
}
void solve(){
    if(H2 == -1){
        int v = -1;
        for(int i = h[H1];i;i = ne[i]){
            v = e[i]; break;
        }
        printf("%d %d\n",v,H1);
        printf("%d %d\n",v,H1);
    }else{
        dfs2(H1,H2);
        printf("%d %d\n",yz,yzfa);
        printf("%d %d\n",yz,H2);
    }
}
int main(){
    // debug_in;

    read(T);
    while(T--){
        idx = 1,mx = inf;
        read(N);
        for(int i = 1;i<=N;i++) h[i] = 0,sz[i] = 0;
        for(int i = 1;i<=N-1;i++){
            int a,b;read(a,b);
            add(a,b);
            add(b,a);
        }
        dfs(1,-1);
        solve();
    }



    return 0;
}