题解：平衡操作（Balancing Act）

题目分析

本题要求找到树中平衡度最小的节点。平衡度定义为删除该节点后，剩余森林中最大子树的节点数。若有多个节点平衡度相同，选择编号最小的节点。这是典型的树的重心（Centroid）问题，树的重心即满足平衡度最小的节点。

方法思路

1. 树的重心性质：

   • 树的重心是删除后最大子树节点数最小的节点。
   • 若树有多个重心，它们相连且最多两个。
   • 重心的平衡度不超过原树节点数的一半（当树节点数为偶数时可能有两个重心，平衡度为 $n/2$）。

2. 算法步骤：

   • 构建邻接表：用邻接表存储树的结构，便于遍历。
   • 深度优先搜索（DFS）：遍历树，计算每个节点的子树大小，并记录删除该节点后最大子树的大小。
   • 寻找重心：遍历所有节点，找到平衡度最小的节点，若平衡度相同则取编号最小的节点。

3. 关键技巧：

   • 在DFS过程中，对于当前节点 $u$，其子树大小为 $size[u]$，删除 $u$ 后，最大子树可能是：
     • 所有子树中的最大大小（通过递归计算子树大小得到）。
     • 父节点方向的子树大小（即 $n - size[u]$，其中 $n$ 为总节点数）。
   • 比较这两部分的最大值，得到该节点的平衡度。

解决代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, index, balance;
vector<int> neighbour[20001];
bool vis[20001];
int subtree[20001];
 
void postTraverse(int i)
{
    vis[i] = true;
    subtree[i] = 1;
    const vector<int>& v = neighbour[i];
    int tmp = 0, j = 0, s = v.size(), k;
    for(; j < s; ++j){
        k = v[j];
        if(!vis[k]){
            postTraverse(k);
            subtree[i] += subtree[k];
            tmp = max(tmp, subtree[k]);
        }
    }
    tmp = max(tmp, n - subtree[i]);
    if(tmp < balance || tmp == balance && i < index){
        balance = tmp;
        index = i;
    }
}
 
int main()
{
    int test, i, x, y;
    for(scanf("%d", &test); test--; ){
        scanf("%d", &n);
    //initialize
        for(i = 1; i <= n; ++i){
            neighbour[i].clear();
            vis[i] = false;
        }
        balance = 20002;
    //input edges
        for(i = 1; i < n; ++i){
            scanf("%d%d", &x, &y);
            neighbour[x].push_back(y);
            neighbour[y].push_back(x);
        }
    //find a leave to be an root
        for(i = 1; i <= n; ++i){
            if(neighbour[i].size() == 1) break;
        }
    //post traverse and find each subtree's nodes count, then solve the problem
        postTraverse(i);
        printf("%d %d\n", index, balance);
    }
    return 0;
}

该算法时间复杂度为 $O(n)$ ，适用于 $n \leq 20000$ 的数据规模，能够高效解决问题。