Kay and Snowflake

GitHub跳转原题关系图返回列表

子树重心必在重儿子的重心到根的祖先路径上；可自底向上继承重儿子的重心并向上跳，均摊 O(n+q)；也可用倍增跳表沿重链向下跳，每次查询 O(log n)，后者可迁移到删边类问题。

OJ: codeforces

题目 ID: 685B

难度:提高+/省选-

标签:树的重心树形DP重链剖分倍增均摊复杂度

创建: 2026-10-29 22:48

更新: 2026-10-30 15:05

后置题目
luogu P5666[CSP-S 2019] 树的重心子树重心的重链单调性定位与倍增/向上跳跃

目录

  1. 形式化题目
  2. 暴力解法
    1. 思路
    2. 代码
    3. 复杂度
    4. 瓶颈
  3. 正解
    1. 关键观察
    2. 思路
    3. 代码
    4. 复杂度
  4. 另一种写法：倍增跳表下降
    1. 两种写法的对照
    2. 代码
  5. 总结

形式化题目

给定一棵以节点 11 为根、包含 nn 个节点的有根树。回答 qq 次独立查询：每次给出一个节点 vv，要求输出以 vv 为根的子树 TvT_v 的任意一个重心。

节点 x∈Tvx \in T_v 是子树 TvT_v 的重心，当且仅当在 TvT_v 中删去 xx 及其关联边后，剩余的所有连通块大小均不超过 ⌊∣Tv∣/2⌋\lfloor |T_v| / 2 \rfloor。

暴力解法

思路

重心的定义要求删去该节点后最大剩余连通块大小不超过总点数的一半。

对于每个查询节点 uu，记以 uu 为根的子树大小为 sz[u]sz[u]。最直接的方法是在 TuT_u 内部逐个枚举每个节点 xx 作为候选重心：

  1. 删去 xx 后，TuT_u 被分为两类连通块：
    • xx 的各个子节点 vv 的子树，大小为 sz[v]sz[v]；
    • 包含 uu 的“上方”连通块，大小为 sz[u]−sz[x]sz[u] - sz[x]。
  2. 检查这些连通块的大小是否均满足 ≤⌊sz[u]/2⌋\le \lfloor sz[u] / 2 \rfloor。首个满足条件的节点即为合法重心。

代码

cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 300005;

int n, q;
int fa[MAXN];
vector<int> children[MAXN];
int sz[MAXN];
int dep[MAXN];

void dfs_sz(int u, int d) {
    dep[u] = d;
    sz[u] = 1;
    for (int v : children[u]) {
        dfs_sz(v, d + 1);
        sz[u] += sz[v];
    }
}

void get_nodes(int u, vector<int>& nodes) {
    nodes.push_back(u);
    for (int v : children[u]) {
        get_nodes(v, nodes);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> q)) return 0;

    for (int i = 2; i <= n; ++i) {
        cin >> fa[i];
        children[fa[i]].push_back(i);
    }

    dfs_sz(1, 1);

    while (q--) {
        int u;
        cin >> u;
        int total = sz[u];
        vector<int> nodes;
        get_nodes(u, nodes);

        int best = -1;
        int best_dep = -1;

        for (int x : nodes) {
            int max_part = total - sz[x];
            for (int v : children[x]) {
                max_part = max(max_part, sz[v]);
            }
            if (max_part <= total / 2) {
                // 深度更深的优先（与 main.cpp 一致：在两个重心时停在子节点处）
                if (dep[x] > best_dep) {
                    best_dep = dep[x];
                    best = x;
                }
            }
        }
        cout << best << "\n";
    }

    return 0;
}

复杂度

  • 遍历以 uu 为根的子树需要 O(sz[u])O(sz[u]) 的时间。
  • 最坏情况下（如整棵树退化为一条长链且多次查询根节点），单次查询需遍历整个树，总时间复杂度为 O(q⋅n)O(q \cdot n)。
  • 空间复杂度为 O(n)O(n)。

瓶颈

每次查询都独立且完整地搜索整棵子树，没有复用树上父子连通块之间重心的拓扑单调性，产生大量重复扫描。在 n,q≤3×105n, q \le 3 \times 10^5 的规模下必然超时（TLE）。

正解

关键观察

要在线性时间内回答所有子树的重心，关键在于利用树的重心在父子之间的位置关系与单调性：

  1. 重心必定落在重子树内： 对于子树 TuT_u，如果某个子节点 vv 满足 sz[v]>⌊sz[u]/2⌋sz[v] > \lfloor sz[u] / 2 \rfloor，则由于各个子节点的子树互不相交，这样的子节点至多只有一个，必然是 uu 的重儿子 heavy[u]heavy[u]。 若删去非 heavy[u]heavy[u] 内部的任何节点，留下的包含 heavy[u]heavy[u] 的连通块大小必然超过一半。因此：

    • 若 sz[heavy[u]]≤⌊sz[u]/2⌋sz[heavy[u]] \le \lfloor sz[u] / 2 \rfloor，uu 本身就是重心；
    • 否则，TuT_u 的重心必然完全落在其重儿子 heavy[u]heavy[u] 的子树内部。

  2. 重心的祖先链单调性： 更进一步，TuT_u 的重心必然位于从 Theavy[u]T_{heavy[u]} 的重心到 uu 的这条祖先路径上。 记 cc 为 heavy[u]heavy[u] 子树的某个已知重心。由重心的定义，cc 的每个子节点的子树大小均满足：

    sz[son]≤⌊sz[heavy[u]]2⌋≤⌊sz[u]2⌋sz[son] \le \left\lfloor \frac{sz[heavy[u]]}{2} \right\rfloor \le \left\lfloor \frac{sz[u]}{2} \right\rfloor
    因此，在 TuT_u 中考查节点 cc 时，它下方的各个子树大小天然符合重心的要求，唯一可能违背条件的是它“上方”的连通块，其大小为 sz[u]−sz[c]sz[u] - sz[c]：

    • 若 sz[u]−sz[c]≤⌊sz[u]/2⌋sz[u] - sz[c] \le \lfloor sz[u] / 2 \rfloor（等价于 2⋅sz[c]≥sz[u]2 \cdot sz[c] \ge sz[u]），则 cc 下方和上方均不超过一半，cc 就是 TuT_u 的重心；
    • 若 sz[u]−sz[c]>⌊sz[u]/2⌋sz[u] - sz[c] > \lfloor sz[u] / 2 \rfloor（等价于 2⋅sz[c]<sz[u]2 \cdot sz[c] < sz[u]），说明 cc 过于靠下，上方连通块过大。此时我们将 cc 沿父节点指针向上跳一步（c←fa[c]c \leftarrow fa[c]）。 向上移动一步后，由于原先的 cc 自身大小满足 sz[c]≤⌊(sz[u]−1)/2⌋≤⌊sz[u]/2⌋sz[c] \le \lfloor (sz[u]-1)/2 \rfloor \le \lfloor sz[u] / 2 \rfloor，新的父节点在包含 cc 的这一侧分支大小不会超过一半，其余轻分支大小更不会超过一半。因此向上跳跃时下方的分支大小始终受控。 我们只需循环检查并向上跳跃，直到首次满足 2⋅sz[c]≥sz[u]2 \cdot sz[c] \ge sz[u] 为止，此时停下的位置即为 TuT_u 的重心。

  3. 均摊复杂度分析： 自底向上（从叶子到根）计算整棵树上每个节点的子树重心： 每个节点 uu 只从其重儿子 heavy[u]heavy[u] 继承重心的起跳点，轻儿子的重心不会作为起跳点被任何人复用。 由于 heavy[u]heavy[u] 与 uu 位于同一条重链上，沿着同一条重链自底向上递推时，重心起跳点与最终停留点的深度是单调不降（深度单调递减）的，不会发生回溯。 因此，整棵树上所有指针跳跃步数之和不超过 nn，递推预处理的总时间复杂度严格为 O(n)O(n)。

思路

  1. 规避递归爆栈： 数据范围 n≤3×105n \le 3 \times 10^5，树可能退化为一条长链。标准递归 DFS 极易导致系统调用栈溢出。 采用 BFS 预先求出整棵树的拓扑遍历序列（自顶向下），然后逆序遍历（从序列末尾到首部），即可在严格常数且无额外栈开销的前提下完成自底向上的后序遍历。

  2. 自底向上递推： 对逆序遍历中的每个节点 uu：

    • 累加其所有子节点的子树大小得到 sz[u]=1+∑v∈children[u]sz[v]sz[u] = 1 + \sum_{v \in children[u]} sz[v]，并记录重儿子 heavy[u]heavy[u]；
    • 若 uu 没有子节点（叶子），则其重心即为自身：ans[u]=uans[u] = u；
    • 若 uu 有子节点，令当前候选指针 c=ans[heavy[u]]c = ans[heavy[u]]。当 2⋅sz[c]<sz[u]2 \cdot sz[c] < sz[u] 时，不断将 cc 替换为其父节点 fa[c]fa[c]。跳跃终止后，记录 ans[u]=cans[u] = c。

  3. 回答查询： 预处理完成后，对每个查询 vv，直接以 O(1)O(1) 输出预存的答案 ans[v]ans[v]。

代码

C++ 实现（使用 BFS 顺序逆序递推，杜绝递归爆栈风险）：

cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 300005;

int n, q;
int fa[MAXN];
vector<int> children[MAXN];
int bfs_order[MAXN];
int sz[MAXN];
int heavy[MAXN];
int ans[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> q)) return 0;

    for (int i = 2; i <= n; ++i) {
        cin >> fa[i];
        children[fa[i]].push_back(i);
    }

    // BFS 遍历生成拓扑序，避免深层递归爆栈
    int head = 0, tail = 0;
    bfs_order[tail++] = 1;
    while (head < tail) {
        int u = bfs_order[head++];
        for (int v : children[u]) {
            bfs_order[tail++] = v;
        }
    }

    // 逆序处理（从叶子到根自底向上）
    for (int i = n - 1; i >= 0; --i) {
        int u = bfs_order[i];
        sz[u] = 1;
        heavy[u] = 0;
        for (int v : children[u]) {
            sz[u] += sz[v];
            if (sz[v] > sz[heavy[u]]) {
                heavy[u] = v;
            }
        }

        if (heavy[u] == 0) {
            ans[u] = u;
        } else {
            int c = ans[heavy[u]];
            // 只要上方连通块大小超过一半，即 2 * sz[c] < sz[u]，就往上跳
            while (2 * sz[c] < sz[u]) {
                c = fa[c];
            }
            ans[u] = c;
        }
    }

    while (q--) {
        int v;
        cin >> v;
        cout << ans[v] << "\n";
    }

    return 0;
}

Python 实现（同样采用显式拓扑序自底向上递推）：

python
import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    q = int(input_data[1])
    
    fa = [0] * (n + 1)
    children = [[] for _ in range(n + 1)]
    
    # 读入父节点
    # input_data[2 : n + 1] 对应 p_2, ..., p_n
    for i in range(2, n + 1):
        p = int(input_data[i])
        fa[i] = p
        children[p].append(i)
    
    # BFS 生成拓扑序，避免递归
    bfs_order = [0] * n
    bfs_order[0] = 1
    head = 0
    tail = 1
    while head < tail:
        u = bfs_order[head]
        head += 1
        for v in children[u]:
            bfs_order[tail] = v
            tail += 1
            
    sz = [1] * (n + 1)
    heavy = [0] * (n + 1)
    ans = [0] * (n + 1)
    
    # 自底向上遍历
    for i in range(n - 1, -1, -1):
        u = bfs_order[i]
        heavy_v = 0
        heavy_sz = 0
        total_sz = 1
        for v in children[u]:
            s = sz[v]
            total_sz += s
            if s > heavy_sz:
                heavy_sz = s
                heavy_v = v
        sz[u] = total_sz
        heavy[u] = heavy_v
        
        if heavy_v == 0:
            ans[u] = u
        else:
            c = ans[heavy_v]
            # 2 * sz[c] < total_sz 说明上方连通块超过一半
            while (sz[c] << 1) < total_sz:
                c = fa[c]
            ans[u] = c
            
    # 回答查询
    out = []
    queries = input_data[n + 1 : n + 1 + q]
    for q_str in queries:
        v = int(q_str)
        out.append(str(ans[v]))
        
    sys.stdout.write("\n".join(out) + "\n")

if __name__ == '__main__':
    main()

复杂度

  • 时间复杂度：预处理构建树并完成自底向上递推耗时 O(n)O(n)，每次询问 O(1)O(1) 回答，总时间复杂度为 O(n+q)O(n + q)。在 n,q=3×105n, q = 3 \times 10^5 的最大测试规模下，实测运行时间远低于时限要求。
  • 空间复杂度：存储邻接表、父节点数组、拓扑序与各节点大小及答案，总空间复杂度为 O(n)O(n)。

另一种写法：倍增跳表下降

上面的均摊 O(n)O(n) 解法靠“继承重儿子的答案再往上跳”把查询摊平，前提是查询之间可以复用。如果把问题换成“每次查询的连通块根和大小都不同”（比如删边后两侧各求重心），就继承不了，必须让每次查询独立可算。

这时用倍增跳表，把“沿重链下走”压成 O(log⁡n)O(\log n)：

up[u][0]=heavy[u],up[u][k]=up[up[u][k−1]][k−1] \mathrm{up}[u][0]=\mathrm{heavy}[u],\qquad \mathrm{up}[u][k]=\mathrm{up}\big[\mathrm{up}[u][k-1]\big][k-1]

查询 TuT_u 的重心时，令 m=sz[u]m=\mathrm{sz}[u]，从 uu 出发，kk 由大到小贪心：

text
u = 待查子树的根，m = sz[u]
for k = LOGN-1 downto 0:
    v = up[u][k]
    若 v != 0 且 2 * sz[v] >= m，则 u = v      // 能跳就跳
返回 u

正确性来自两个单调性：sz\mathrm{sz} 沿重链严格递减，所以“2 sz[x]⩾m2\,\mathrm{sz}[x]\geqslant m”在链上是从真到假的前缀，贪心跳到不能再跳就正好停在最后一个满足它的点上；而跳的每一步都要求 2 sz[v]⩾m2\,\mathrm{sz}[v]\geqslant m，保证 vv 子树占了至少一半，重心不会在别的分支里。

两种写法的对照

均摊 O(n)O(n) 解法 倍增解法
起点 继承 ans[heavy[u]] 从 u 出发
方向 沿 fa 向上跳 沿 heavy 向下跳
依赖 自底向上离线递推，可继承上一条结果 不依赖任何其他查询
单次查询 均摊 O(1)O(1) O(log⁡n)O(\log n)
总复杂度 O(n+q)O(n+q) O((n+q)log⁡n)O((n+q)\log n)
空间 O(n)O(n) O(nlog⁡n)O(n\log n)

两个方向是对偶的：自底向上能复用就向上跳，无法复用就向下倍增。本题两种都能过；但后者能直接搬到删边类题目上（见 [[[p: luogu-P5666]]]）。

代码

倍增跳表下降实现（每次查询独立，O(log⁡n)O(\log n)）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-30 15:02
 * update_at: 2026-10-30 15:02
 */
// main-jump.cpp：CF685B 的倍增跳表解法。
// 与 main.cpp 的均摊 O(n) 解法方向相反：这里沿 heavy 链「向下」跳，
// 每次查询独立 O(log n)，不依赖任何已算好的答案。
// 好处是查询之间无耦合，正是 P5666 删边后查两侧连通块所需的能力。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
const int LOGN = 20; // 2^19 = 524288 > 3e5

int n, q;
vector<int> g[MAXN];        // 邻接表（无向，dfs 时按 fa 定向）
int fa[MAXN];               // fa[u]：父亲，根的 fa 为 0
int sz[MAXN];               // sz[u]：子树大小（含自己）
int son[MAXN];              // son[u]：重儿子，叶子为 0
int up[MAXN][LOGN];         // up[u][k]：沿 heavy 链从 u 向下跳 2^k 步到达的点

// 一遍 DFS：往下填 fa，回溯时汇总 sz、选出重儿子，并顺手定下跳表第 0 层。
void dfs(int u, int p) {
    fa[u] = p;
    sz[u] = 1;
    son[u] = 0;
    for (auto v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v; // sz[0] 恒为 0，叶子自然没有重儿子
    }
    up[u][0] = son[u];
}

// 求“以 u 为根、大小为 sz[u] 的子树”的一个重心。
// 沿重链向下走：只要某个方向的点还不少于子树的一半，重心必在那一侧；
// 重链上 sz 严格递减，所以“2*sz[x] >= m”沿链单调，可倍增贪心下降。
int centroid_of_subtree(int u) {
    int m = sz[u];
    for (int k = LOGN - 1; k >= 0; --k) {
        int v = up[u][k];
        if (v != 0 && sz[v] * 2 >= m) u = v; // 能跳就跳
    }
    return u; // 子节点方向都不足一半，且上方块 m - sz[u] 也不超过一半
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        g[p].push_back(i);
        g[i].push_back(p);
    }

    dfs(1, 0);

    // 按层搭跳表：up[u][k] = up[ up[u][k-1] ][k-1]。
    // 必须外层枚举 k：第 k 层只依赖第 k-1 层。
    for (int k = 1; k < LOGN; k++) {
        for (int u = 1; u <= n; u++) {
            up[u][k] = up[up[u][k - 1]][k - 1];
        }
    }

    while (q--) {
        int v;
        cin >> v;
        cout << centroid_of_subtree(v) << '\n';
    }

    return 0;
}

总结

  • 树的重心性质十分优雅：子树的重心必定落在重儿子的重心到根节点的祖先路径上。
  • 通过「继承重儿子重心 + 向上试探跳跃」的策略，避开了对每棵子树的全量搜索。因为起跳点仅沿重链单向向上移动，均摊证明保障了整棵树的总跳跃次数不超过 nn 次。
  • 若查询之间无法复用（例如删边后每次的连通块都不同），就改用倍增跳表沿重链向下跳，把单次查询压到 O(log⁡n)O(\log n)；这是 [[[p: luogu-P5666]]] 所需的形式。
  • 在具体工程实现上，使用 BFS 拓扑序逆序遍历替代递归 DFS，消除了长链退化场景下的爆栈隐患，保证了代码在极端测试数据下的稳健性与高执行效率。