题目简述

给定一棵 $n$ 个节点的树。允许执行一次操作：切断一条边，再添加一条边，使得操作后的图仍然是一棵树。要求操作后树的重心唯一。输出任意一种可行的操作（切掉的边和添加的边）。

重心定义与性质

• 重心：树中的一个节点，当删除该节点后，得到的若干连通分量中，最大的连通分量的大小最小。
  等价定义：以该节点为根时，所有子树的大小都不超过 $\lfloor n/2 \rfloor$。

• 重要性质：一棵树的重心个数为 $1$ 或 $2$。
  若有两个重心，则它们必定相邻（即存在边直接连接）。

解题思路

1. 找出所有重心

通过一次 DFS 可以计算：

• $siz[u]$：以 $u$ 为根的子树大小（任选一个根，例如 $1$）。
• $maxSub[u] = \max(\max_{v\in children(u)} siz[v],\; n - siz[u])$，即删除 $u$ 后最大连通块的大小。
• 全局最小值 $Min = \min_{u} maxSub[u]$。
• 所有满足 $maxSub[u] = Min$ 的节点即为重心，个数为 $1$ 或 $2$。

2. 分类讨论

情况一：只有一个重心

此时操作可以什么都不做，即切掉任意一条边（例如第一条边）并原样加回。这样树不变，重心仍然唯一。

情况二：有两个重心

设两个重心为 $x$ 和 $y$，且 $x$ 与 $y$ 相邻（由性质保证）。
不妨设 $x$ 是 $y$ 的父亲（若不然，交换 $x$ 与 $y$），则 $y$ 的子树大小必为 $\frac{n}{2}$（因为 $x$ 和 $y$ 都是重心，删除 $y$ 后最大连通块为 $\max(\text{其余部分}, n - siz[y]) = \frac{n}{2}$，可推出 $siz[y] = \frac{n}{2}$）。

操作：

1. 在 $y$ 的子树中（避开 $x$ 的方向）找到一个叶子节点 $leaf$。
2. 切断边 $(y, leaf)$。
3. 添加边 $(x, leaf)$。

正确性证明：

• 切断 $(y, leaf)$ 后，$y$ 的子树大小减少 $1$（因为 $leaf$ 是叶子），变为 $\frac{n}{2} - 1$；同时 $x$ 的某个子树（即原 $y$ 的子树）大小也减少 $1$。
• 添加 $(x, leaf)$ 后，$x$ 的某个子树（即新加入的 $leaf$ 分支）大小变为 $1$，而 $y$ 的子树大小不变（因为 $leaf$ 原本属于 $y$ 的子树，现在被移到了 $x$ 的直接子树上）。
• 此时，$y$ 的最大连通块大小变为 $\frac{n}{2} + 1$（因为 $x$ 方向的分支大小变为 $\frac{n}{2} + 1$），而 $x$ 的最大连通块大小仍为 $\frac{n}{2}$。因此 $x$ 成为唯一重心。

重心查找的算法实现

使用树形 DP，任选一个根（如节点 $1$），DFS 计算每个节点的子树大小 $siz[u]$，并计算 $maxSub[u] = \max(\max_{v\in son(u)} siz[v],\; n - siz[u])$，同时记录全局最小值 $Min$。
第二次遍历所有节点，若 $maxSub[u] = Min$，则 $u$ 是重心。

代码实现细节（参考标程）

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
int head[maxn],cnt=0,nxt[maxn<<1],to[maxn<<1];

void add(int u,int v) {
    cnt++;
    to[cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

int n,siz[maxn],Max[maxn],Min,a[maxn],cntt,tmp2;

void dfs(int x,int fa) {
    siz[x]=1;
    Max[x]=0;   // 初始化为0，后面更新
    for(int i=head[x];i;i=nxt[i]) {
        int v=to[i];
        if(v==fa) continue;
        dfs(v,x);
        siz[x]+=siz[v];
        Max[x]=max(Max[x], siz[v]);
    }
    Max[x]=max(Max[x], n - siz[x]);   // 考虑向上部分
    if(Max[x] < Min) Min = Max[x];
}

// 在子树中寻找一个叶子节点（不向 fa 方向走）
int find(int x,int fa) {
    for(int i=head[x];i;i=nxt[i]) {
        int v=to[i];
        if(v==fa) continue;
        tmp2 = x;          // 记录当前节点的父节点，即切边的端点之一
        return find(v, x);
    }
    return x;              // 叶子节点
}

int main() {
    int T; cin>>T;
    while(T--) {
        cnt = cntt = 0;
        scanf("%d",&n);
        Min = n+1;
        memset(head,0,sizeof head);
        for(int i=1;i<n;i++) {
            int x,y; scanf("%d%d",&x,&y);
            add(x,y); add(y,x);
        }
        dfs(1,0);

        // 收集所有重心
        for(int i=1;i<=n;i++)
            if(Max[i]==Min) a[++cntt]=i;

        if(cntt==1) {   // 唯一重心
            // 输出任意一条边，这里取第一个邻接点
            printf("%d %d\n%d %d\n", a[1], to[head[a[1]]], a[1], to[head[a[1]]]);
        } else {        // 两个重心
            // 从第二个重心 a[2] 的子树中找一个叶子（避开 a[1]）
            int leaf = find(a[2], a[1]);
            printf("%d %d\n%d %d\n", tmp2, leaf, a[1], leaf);
        }
    }
    return 0;
}

关键点说明

• Max[x] 初始化为 $0$，因为叶子节点的最大子树大小就是 $n - 1$（向上部分），但比较时不影响。
• 只有一个重心时，输出重心的第一条邻接边（存在性由 $n\ge3$ 保证）。
• 两个重心时，find(a[2], a[1]) 从 $a[2]$ 出发，不向 $a[1]$ 方向走，最终返回叶子节点，同时用 tmp2 记录其父节点，即切边的一端。输出切边 (tmp2, leaf) 和加边 (a[1], leaf)。

复杂度分析

• 时间复杂度：$O(n)$，每个节点访问常数次。
• 空间复杂度：$O(n)$，邻接表存储。

总结

本题的关键在于掌握树的重心性质，并根据重心个数分类构造操作。代码实现简洁，利用两次 DFS 即可完成。