消息传递

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

以任意点为起点在树上并行扩散消息,用两次树形 DP 求出每个点的子树与父亲方向耗时,换根时靠前后缀最大值 O(1) 剔除一个方向,取最小值加 1 即答案。

OJ: roj

题目 ID: 1773

难度:提高+/省选-

标签:树形DP换根DP贪心python

创建: 2026-10-08 01:41

更新: 2026-10-08 01:41

形式化题目

给定一棵 NN 个点的无向树(输入给出编号 11 为国王以及每个点的直接上级,等价于给出 一棵以 11 为根的树;但消息既能向上级传也能向下属传,所以约束只落在无向边上)。 时刻 00 选定一个起点 ss,花费 11 单位时间把消息告诉 ss(即 ss 在时刻 11 得知消息)。 此后每个单位时间内,每个已知消息的点都可以向至多一个尚未知情的邻居传消息, 各点同时进行、互不影响。

记 g(s)g(s) 为"若 ss 在 00 时刻就已知消息,传遍全树所需的时间",则总耗时为 1+g(s)1 + g(s)。 要求输出

min⁡s(1+g(s)),\min_{s} \bigl(1 + g(s)\bigr),

以及所有取到该最小值的起点编号,按升序用空格分隔。

正解

思路

朴素做法。 枚举起点 ss,把 ss 当作根做一次树形 DP。对每个点 uu 定义

f[u]=「u 已知消息时,u 的子树全部知情所需的时间」.f[u] = \text{「} u \text{ 已知消息时,} u \text{ 的子树全部知情所需的时间」}.

若 uu 有 kk 个儿子,它每秒只能通知一个儿子,所以耗时大的儿子要优先通知: 把儿子的 ff 值从大到小排序成 f1≥f2≥⋯≥fkf_1 \ge f_2 \ge \dots \ge f_k,第 ii 个儿子在第 ii 秒被通知, 于是

f[u]=max⁡1≤i≤k(i+fi),叶子 f[u]=0.f[u] = \max_{1 \le i \le k} \bigl(i + f_i\bigr), \qquad \text{叶子 } f[u] = 0 .

g(s)=f[s]g(s) = f[s],对每个起点做一遍就是 O(N2log⁡N)O(N^2 \log N)。N≤200 000N \le 200\,000 时 N2N^2 达到 4×10104 \times 10^{10},1000 ms 内不可能跑完,必须换根。

换根:把「删掉一个方向」的答案用前后缀最大值 O(1)O(1) 求出。 起点从 uu 挪到相邻的 vv 时, 整棵树只有 uu 的"方向清单"少了一项。所谓方向,就是把 uu 的每个邻居看成一个待通知的 分支:儿子 cc 方向的耗时是 f[c]f[c],父亲方向(记为 up[u]up[u])的耗时是"砍掉 uu 子树后, 剩下的那一大块从 uu 开始扩散完的时间"。

把 uu 的全部 mm 个方向按耗时降序排成 w1≥w2≥⋯≥wmw_1 \ge w_2 \ge \dots \ge w_m,预处理

pref[i]=max⁡1≤j≤i(j+wj),suff[i]=max⁡i≤j≤m((j−1)+wj). pref[i] = \max_{1 \le j \le i} \bigl(j + w_j\bigr), \qquad suff[i] = \max_{i \le j \le m} \bigl((j - 1) + w_j\bigr).

suffsuff 里刻意写成 j−1j-1:一旦排在第 idxidx 位的方向被剔除, 排在它后面的方向在队列里全部前移一位,耗时从 j+wjj + w_j 变成 (j−1)+wj(j-1) + w_j。 于是

up[v]=max⁡(pref[idx−1],  suff[idx+1]),up[v] = \max\bigl(pref[idx-1],\; suff[idx+1]\bigr),

其中 idxidx 是 vv 在降序序列里的位置;idx=1idx = 1 或 idx=midx = m 时对应的越界项取 00 (表示那一侧没有方向,不需要再等)。

同时 uu 自己的答案就是整张清单的前缀最大值:

g[u]=pref[m](度为 0 时 g[u]=0).g[u] = pref[m] \quad(\text{度为 } 0 \text{ 时 } g[u] = 0).

整个流程只需两次遍历:先以 11 为根自底向上算出所有 f[u]f[u],再自顶向下按上式算出 所有 up[v]up[v] 与 g[u]g[u],最后取 1+min⁡g[u]1 + \min g[u] 并顺序扫出所有最优起点。

用第二个样例核对一遍。 树的边为 1 ⁣− ⁣21\!-\!2、1 ⁣− ⁣31\!-\!3、3 ⁣− ⁣43\!-\!4、3 ⁣− ⁣83\!-\!8、4 ⁣− ⁣54\!-\!5、 4 ⁣− ⁣64\!-\!6、4 ⁣− ⁣74\!-\!7。以 11 为根先算 ff:f[4]=max⁡(1,2,3)=3f[4] = \max(1,2,3) = 3(三个叶子儿子)、 f[3]=max⁡(1+3,  2+0)=4f[3] = \max(1 + 3,\; 2 + 0) = 4(儿子 44 与 88)、f[8]=0f[8] = 0。 再换根:

起点 uu uu 的方向清单(降序) g[u]g[u] 1+g[u]1 + g[u]
1 f[3]=4,  f[2]=0f[3]=4,\; f[2]=0 max⁡(5,2)=5\max(5,2)=5 6
2 up[2]=5up[2]=5(11 一侧只剩 33 方向) 1+5=61+5=6 7
3 f[4]=3,  up[3]=1,  f[8]=0f[4]=3,\; up[3]=1,\; f[8]=0 max⁡(4,3,3)=4\max(4,3,3)=4 5
4 up[4]=2,  f[5]=f[6]=f[7]=0up[4]=2,\; f[5]=f[6]=f[7]=0 max⁡(3,2,3,4)=4\max(3,2,3,4)=4 5
5 / 6 / 7 up[⋅]=3up[\cdot]=3 1+3=41+3=4 5
8 up[8]=4up[8]=4 1+4=51+4=5 6

最小值 44 出现在 3,4,5,6,73,4,5,6,7,加上最初的 11 单位时间得 55,与样例输出 5 / 3 4 5 6 7 完全一致。注意 up[3]=1up[3]=1 这一项:它来自节点 11 的清单 [4,0][4,0] 去掉 f[3]f[3] 后剩下的 f[2]=0f[2]=0,虽然值为 00,但 33 把它排在第 22 位, 仍然要额外花 22 秒,所以是 max⁡(4, 2+0, 3+0)=4\max(4,\,2+0,\,3+0)=4 而不是 4+14+1。

边界 N=1N = 1。 只有国王一个人,00 时刻花 11 单位时间通知他,答案为第一行 1、 第二行 1;此时 uu 的方向清单为空,g[1]=0g[1] = 0,公式给出的 1+0=11 + 0 = 1 依然正确。

代码

Python 版:

python
#!/usr/bin/env python3
# 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-08 01:41
# update_at: 2026-10-08 01:41

import sys

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Tree = list[list[int]]  # 邻接表:Tree[u] 是 u 的所有邻居(下标 0 空置)


def root_order(adj: Tree) -> tuple[list[int], list[int]]:
    """以 1 为根 BFS 定序,返回 (访问序, 父亲数组),父亲一定排在儿子前面。"""
    par = [0] * len(adj)
    order = [1]
    for u in order:
        for v in adj[u]:
            if v != par[u]:
                par[v] = u
                order.append(v)
    return order, par


def subtree_time(adj: Tree, par: list[int], order: list[int]) -> list[int]:
    """f[u]:u 在 0 时刻已知消息时,u 的子树全部知情所需的时间。

    儿子降序发送:第 i 个儿子在第 i 秒被通知,故 f[u] = max(i + f_i),叶子为 0。
    """
    f = [0] * len(adj)
    for u in reversed(order):
        sons = sorted((f[v] for v in adj[u] if v != par[u]), reverse=True)
        f[u] = max((i + x for i, x in enumerate(sons, 1)), default=0)
    return f


def reroot(adj: Tree, par: list[int], order: list[int], f: list[int]) -> list[int]:
    """自顶向下换根,返回 g[u]:u 在 0 时刻已知消息时传遍全树的时间。

    把 u 的所有方向降序排成 w[1..m](儿子方向取 f[son],父亲方向取 up[u]),则
    pref[i] = max(j + w_j) (j<=i)、suff[i] = max(j-1 + w_j) (j>=i);
    剔除第 idx 位的儿子 v 后,后面各项集体前移一位,于是
    up[v] = max(pref[idx-1], suff[idx+1]),而 g[u] = pref[m]。
    """
    up = [0] * len(adj)
    g = [0] * len(adj)
    for u in order:
        items = sorted(
            ((up[u] if v == par[u] else f[v], v) for v in adj[u]),  # (方向耗时, 邻居)
            reverse=True,
        )
        m = len(items)
        pref = [0] * (m + 1)
        for i in range(1, m + 1):
            pref[i] = max(pref[i - 1], i + items[i - 1][0])
        suff = [0] * (m + 2)
        for i in range(m, 0, -1):
            suff[i] = max(suff[i + 1], i - 1 + items[i - 1][0])  # -1:删一项后整体前移
        g[u] = pref[m]
        for i in range(1, m + 1):
            v = items[i - 1][1]
            if par[v] == u:  # v 是 u 的儿子,它拿到的正是"父亲方向"耗时
                up[v] = max(pref[i - 1], suff[i + 1])
    return g


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    adj: Tree = [[] for _ in range(n + 1)]
    for i in range(2, n + 1):
        p = next(data)  # 编号 i 的人的直接上级
        adj[p].append(i)
        adj[i].append(p)  # 消息双向可传,按无向边建树
    order, par = root_order(adj)
    g = reroot(adj, par, order, subtree_time(adj, par, order))
    best = min(g[1:])
    print(1 + best)  # 最初通知那个人要花 1 单位时间
    print(" ".join(str(u) for u in range(1, n + 1) if g[u] == best))


if __name__ == "__main__":
    solve()

C++ 版(同一算法,手写链式前向星 + BFS 定序,避免链状数据爆递归栈):

cpp
// ===========================================================================
//  题目:消息传递(ROJ 1773 / 信息学奥赛一本通 · 高手训练篇 动态规划)
//  算法:树上换根 DP + 前缀 / 后缀最大值
// ---------------------------------------------------------------------------
//  1. 上下级关系只是一棵无向树:消息既能上报也能下达,所以直接按无向边建树。
//  2. 以 1 号(国王)为根,自底向上求 f[u]:u 在 0 时刻收到消息时,
//     把消息传遍 u 的整棵子树所需的时间。
//     若 u 有 k 个儿子,按 f 从大到小排序后第 i 个儿子在第 i 秒被通知,
//     故 f[u] = max_i ( i + f[son_i] ),叶子 f[u] = 0。
//  3. 自顶向下换根:把 u 的所有“方向”放在一起降序排序成 w[1..m]
//     (儿子方向取 f[son],父亲方向取 up[u]),预处理
//        pref[i] = max_{j<=i} ( j + w[j] )
//        suff[i] = max_{j>=i} ( j - 1 + w[j] )
//     去掉排在第 idx 位的儿子 v 之后,u 这一侧从 u 开始扩散完的时间
//        up[v] = max( pref[idx-1], suff[idx+1] )
//     这正是 v 作为根时“父亲方向”的耗时(后面的元素集体前移一位)。
//  4. g[u] = pref[m](u 无邻居时为 0)= u 在 0 时刻收到消息后传遍全树的时间。
//     答案第一行 = 1 + min g[u](初始通知那个人要花 1 单位时间),
//     第二行 = 所有取到最小值的 u,按编号升序输出。
//  复杂度:时间 O(N log N)(每个点的邻居排序,Σd = 2N-2),空间 O(N)。
// ===========================================================================
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 200005;

int n;
int head[MAXN], nxt[2 * MAXN], to[2 * MAXN], ecnt;  // 邻接表(链式前向星)
int par[MAXN];    // 以 1 为根时的父亲
int ord[MAXN];    // BFS 序(父亲一定排在儿子前面)
int f[MAXN];      // f[u]:u 的子树内部扩散耗时
int up_[MAXN];    // up_[u]:u 的父亲方向那半棵树的扩散耗时
int g[MAXN];      // g[u]:以 u 为起点时,全树扩散耗时(不含最初那 1 单位)

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

int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        int p;
        scanf("%d", &p);
        addEdge(p, i);
        addEdge(i, p);
    }

    // 第一步:BFS 定序(避免 N=200000 的链把递归栈爆掉)
    int cnt = 0;
    ord[++cnt] = 1;
    par[1] = 0;
    for (int i = 1; i <= cnt; i++) {
        int u = ord[i];
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v == par[u]) continue;
            par[v] = u;
            ord[++cnt] = v;
        }
    }

    // 第二步:自底向上求 f[u]
    for (int i = n; i >= 1; i--) {
        int u = ord[i];
        vector<int> vals;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v != par[u]) vals.push_back(f[v]);
        }
        sort(vals.begin(), vals.end(), greater<int>());  // 耗时大的子树优先通知
        int best = 0;
        for (int j = 0; j < (int)vals.size(); j++) {
            best = max(best, (j + 1) + vals[j]);
        }
        f[u] = best;
    }

    // 第三步:自顶向下换根,顺便算出 g[u]
    for (int i = 1; i <= n; i++) {
        int u = ord[i];
        vector<pii> items;  // (该方向的耗时, 该方向的邻居编号)
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v == par[u]) {
                if (u != 1) items.push_back(pii(up_[u], v));  // 父亲方向
            } else {
                items.push_back(pii(f[v], v));                // 儿子方向
            }
        }
        sort(items.begin(), items.end(), greater<pii>());
        int m = items.size();
        vector<int> pref(m + 2, 0), suff(m + 3, 0);
        for (int j = 1; j <= m; j++) pref[j] = max(pref[j - 1], j + items[j - 1].first);
        for (int j = m; j >= 1; j--) suff[j] = max(suff[j + 1], (j - 1) + items[j - 1].first);
        g[u] = pref[m];
        for (int j = 1; j <= m; j++) {
            int v = items[j - 1].second;
            if (par[v] == u) {  // v 是 u 的儿子:算出 v 的父亲方向耗时
                up_[v] = max(pref[j - 1], suff[j + 1]);
            }
        }
    }

    // 第四步:统计答案
    int best = g[1];
    for (int u = 2; u <= n; u++) best = min(best, g[u]);
    int T = 1 + best;  // 初始通知要花 1 单位时间

    printf("%d\n", T);
    bool first = true;
    for (int u = 1; u <= n; u++) {
        if (g[u] == best) {
            if (!first) printf(" ");
            printf("%d", u);
            first = false;
        }
    }
    printf("\n");
    return 0;
}

复杂度

  • 时间:第一次 DP 与换根各遍历每个点一次,代价是对该点的邻居排序。 设点 uu 的度数为 dud_u,树满足 ∑du=2N−2\sum d_u = 2N - 2,故排序总耗时为 ∑O(dulog⁡du)≤O(Nlog⁡N)\sum O(d_u \log d_u) \le O(N \log N)(最坏是菊花图,根要排 N−1N-1 项); 前后缀数组的构建与回填 upup 都是 O(du)O(d_u)。总时间 O(Nlog⁡N)O(N \log N), N=2×105N = 2 \times 10^5 时约 3.6×1063.6 \times 10^6 次基本运算,实测远低于 1000 ms。
  • 空间:邻接表 O(N)O(N),f/up/g/pref/sufff / up / g / pref / suff 各 O(N)O(N), 单个点的临时清单最坏 O(N)O(N)(菊花图根节点),总空间 O(N)O(N),远低于 256 MB。
  • 与 C++ 解法的关系:两者是同一套换根 DP,复杂度同为 O(Nlog⁡N)O(N \log N)。 Python 版把两次遍历都写成迭代(BFS 序 + 逆序 / 正序), 避免 N=2×105N = 2 \times 10^5 的链触发递归深度上限;由于核心工作是排序, 常数主要在 sorted 上,本题不存在 Python 特有的算法降级。

总结

  • 先定义好"一个方向的耗时":f[u]f[u] 管子树、up[u]up[u] 管父亲那一侧, 两者语义对称,换根转移才能写得干净。
  • 大耗时分支优先通知:给定一组方向的耗时,最优策略是把它们降序发送, 最大完成时间 max⁡i(i+wi)\max_i (i + w_i);这一步的贪心交换论证是本题的出发点。
  • 删一项的极值用前后缀维护:换根时唯一的变化是清单少一项、后面的项集体前移, 前缀最大值配一个 −1-1 偏移的后缀最大值就能 O(1)O(1) 回答, 这是"O(N2)O(N^2) 枚举根 →\to O(Nlog⁡N)O(N \log N)"的关键一步。
  • 别忘了初始的 11 单位时间:题目是"用 1 单位时间把消息告诉某一个人", 所以输出要写 1+min⁡g[u]1 + \min g[u],直接输出 gg 会全部差 1。
  • 本题素材说明:本题来自信息学奥赛一本通《高手训练篇》,与洛谷 P2018《消息传递》 同源。仓库内 data/ 由 data.py 自动生成(覆盖链、星、完全二叉树、随机树、 20%/50%/100%20\%/50\%/100\% 各档规模),因此测试数据是自造的,出题意图与官方原题可能存在偏差; 题面与数据均已按上述模型逐点核对通过。