以任意点为起点在树上并行扩散消息,用两次树形 DP 求出每个点的子树与父亲方向耗时,换根时靠前后缀最大值 O(1) 剔除一个方向,取最小值加 1 即答案。
OJ: roj
题目 ID: 1773
难度:提高+/省选-
标签:树形DP换根DP贪心python
创建: 2026-10-08 01:41
更新: 2026-10-08 01:41
形式化题目
给定一棵
记
以及所有取到该最小值的起点编号,按升序用空格分隔。
正解
思路
朴素做法。 枚举起点
若
换根:把「删掉一个方向」的答案用前后缀最大值
把
其中
同时
整个流程只需两次遍历:先以
用第二个样例核对一遍。 树的边为
| 起点 |
|||
|---|---|---|---|
| 1 | 6 | ||
| 2 | 7 | ||
| 3 | 5 | ||
| 4 | 5 | ||
| 5 / 6 / 7 | 5 | ||
| 8 | 6 |
最小值 5 / 3 4 5 6 7 完全一致。注意
边界 1、
第二行 1;此时
代码
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 定序,避免链状数据爆递归栈):
// ===========================================================================
// 题目:消息传递(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 与换根各遍历每个点一次,代价是对该点的邻居排序。
设点
的度数为 ,树满足 ,故排序总耗时为 (最坏是菊花图,根要排 项); 前后缀数组的构建与回填 都是 。总时间 , 时约 次基本运算,实测远低于 1000 ms。 - 空间:邻接表
, 各 , 单个点的临时清单最坏 (菊花图根节点),总空间 ,远低于 256 MB。 - 与 C++ 解法的关系:两者是同一套换根 DP,复杂度同为
。 Python 版把两次遍历都写成迭代(BFS 序 + 逆序 / 正序), 避免 的链触发递归深度上限;由于核心工作是排序, 常数主要在 sorted上,本题不存在 Python 特有的算法降级。
总结
- 先定义好"一个方向的耗时":
管子树、 管父亲那一侧, 两者语义对称,换根转移才能写得干净。 - 大耗时分支优先通知:给定一组方向的耗时,最优策略是把它们降序发送,
最大完成时间
;这一步的贪心交换论证是本题的出发点。 - 删一项的极值用前后缀维护:换根时唯一的变化是清单少一项、后面的项集体前移,
前缀最大值配一个
偏移的后缀最大值就能 回答, 这是" 枚举根 "的关键一步。 - 别忘了初始的
单位时间:题目是"用 1 单位时间把消息告诉某一个人", 所以输出要写 ,直接输出 会全部差 1。 - 本题素材说明:本题来自信息学奥赛一本通《高手训练篇》,与洛谷 P2018《消息传递》
同源。仓库内
data/由data.py自动生成(覆盖链、星、完全二叉树、随机树、各档规模),因此测试数据是自造的,出题意图与官方原题可能存在偏差; 题面与数据均已按上述模型逐点核对通过。