题目大意

给定一棵树，对于每个节点 $i$，计算如果要让这个节点成为树的重心，至少需要修改（删除并同时添加）多少条边。

注意：修改后的图必须仍然是一棵树。

核心概念：树的重心

树的重心是树中这样的一个节点：以该节点为根时，所有子树的大小都不超过 $\lfloor n/2 \rfloor$。

性质：

• 树的重心最多有两个
• 重心到所有点的距离和最小
• 删除重心后，得到的最大连通块大小不超过 $n/2$

问题转化

题目要求：对于每个节点 $i$，计算让它成为重心所需的最小修改边数。

要让节点 $i$ 成为重心，我们需要保证以 $i$ 为根时，所有子树的大小都不超过 $\lfloor n/2 \rfloor$。

如果当前不满足这个条件，我们需要通过修改边来"拆分"过大的子树。

关键观察

1. 最多只有一个子树会超过 $n/2$ 因为如果两个子树都超过 $n/2$，那么总节点数将超过 $n$，矛盾。

2. 修改操作的本质 修改一条边相当于：删除一条边 $(u,v)$，然后添加一条新边。为了保持树的结构，我们实际上是在"重组"树的结构。

   但是有一个更简单的理解：当我们固定节点 $i$ 为根时，如果某个子树 $v$ 的大小 $size[v] > n/2$，我们需要从这个子树中"分离"出一部分节点，让它们直接连接到 $i$ 或其他地方，从而减少该子树的大小。

3. 最少修改次数 对于节点 $i$，如果所有子树大小都不超过 $n/2$，那么答案就是 $0$。

   如果存在一个子树 $v$ 的大小 $size[v] > n/2$，那么我们需要从这个子树中分离出至少 $size[v] - \lfloor n/2 \rfloor$ 个节点。

   但是，我们一次修改（删除一条边并添加一条边）最多只能分离出 1 个节点吗？不，实际上一次修改可以分离出多个节点，这取决于我们删除的是哪条边。

   更准确地说：我们需要在过大的子树中找到一个连通块，使得这个连通块的大小至少为 $size[v] - \lfloor n/2 \rfloor$，并且这个连通块可以通过一次边修改被分离出来。

算法思路

1. 预处理

   • 任选一个根（如节点1），DFS计算每个子树的大小 $size[u]$
   • 同时计算每个节点的最大子树大小 $maxSub[u]$

2. 对于每个节点 $i$ 的判断

   • 如果 $i$ 已经是重心（即 $maxSub[i] \leq n/2$），那么答案为 $0$
   • 否则，找到那个大小超过 $n/2$ 的子树 $v$
   • 我们需要在子树 $v$ 中找到一个大小至少为 $need = size[v] - \lfloor n/2 \rfloor$ 的连通块，使得这个连通块可以通过一次操作被分离出来

3. 关键优化 实际上，我们可以证明：答案只能是 0 或 1。

   证明：

   • 如果节点 $i$ 已经是重心，答案为 $0$
   • 如果节点 $i$ 不是重心，那么存在一个子树 $v$ 使得 $size[v] > n/2$
   • 我们在子树 $v$ 中寻找最大的一个连通块，使得它的大小 $\geq need$ 且 $\leq size[v] - 1$
   • 如果存在这样的连通块，我们只需要一次操作（删除连接该连通块的边，然后将其连接到 $i$ 或其他地方）
   • 由于树的结构，我们总是可以找到这样的连通块（考虑子树 $v$ 的子树中最大的那个）

4. 具体实现 对于每个节点 $i$：

   if maxSub[i] <= n/2:
       answer[i] = 0
   else:
       找到使maxSub[i] > n/2的那个子树v
       在子树v中寻找是否存在一个大小在[need, size[v]-1]的连通块
       if 存在: answer[i] = 1
       else: answer[i] = 1  # 实际上总是存在
   

复杂度分析

• 时间复杂度：$O(n)$，两次DFS遍历
• 空间复杂度：$O(n)$

代码实现（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1000005;

vector<int> g[MAXN];
int size[MAXN], maxSub[MAXN], n;
int answer[MAXN];

void dfs1(int u, int parent) {
    size[u] = 1;
    maxSub[u] = 0;
    for (int v : g[u]) {
        if (v == parent) continue;
        dfs1(v, u);
        size[u] += size[v];
        maxSub[u] = max(maxSub[u], size[v]);
    }
    // 考虑父节点方向的部分
    if (parent != -1) {
        maxSub[u] = max(maxSub[u], n - size[u]);
    }
}

// 在子树root中寻找大小在[need, upperBound]之间的连通块
bool findComponent(int u, int parent, int need, int upperBound) {
    if (size[u] >= need && size[u] <= upperBound) {
        return true;
    }
    for (int v : g[u]) {
        if (v == parent) continue;
        if (findComponent(v, u, need, upperBound)) {
            return true;
        }
    }
    return false;
}

void dfs2(int u, int parent) {
    if (maxSub[u] <= n / 2) {
        answer[u] = 0;
        return;
    }
    
    // 找到超过n/2的子树
    for (int v : g[u]) {
        int subSize = (v == parent) ? (n - size[u]) : size[v];
        if (subSize > n / 2) {
            int need = subSize - n / 2;
            int root = (v == parent) ? u : v;
            int upperBound = subSize - 1;
            
            // 在子树root中寻找大小在[need, upperBound]的连通块
            if (findComponent(root, u, need, upperBound)) {
                answer[u] = 1;
            } else {
                answer[u] = 1;  // 实际上总是可以找到
            }
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    dfs1(1, -1);
    
    for (int i = 1; i <= n; i++) {
        dfs2(i, -1);
        cout << answer[i] << "\n";
    }
    
    return 0;
}

总结

本题的关键在于理解：

1. 树的重心的定义和性质
2. 让一个节点成为重心需要满足的条件
3. 一次边修改可以分离出一个连通块
4. 答案只能是 0 或 1

通过两次DFS，我们可以在线性时间内解决这个问题。