把双方偏好统一成二元组 (Bob, -Alice) 的字典序,在树上按深度奇偶交替做极小极大 DP,自底向上 O(n) 合并子树。
OJ: roj
题目 ID: 1818
难度:普及+/提高-
标签:树形DP博弈论极小极大搜索python
创建: 2026-10-08 06:36
更新: 2026-10-08 06:36
形式化题目
给定一棵
设结束时 Alice 共得
- Alice:先让
尽可能小,在 相同时让自己 尽可能大; - Bob:先让自己
尽可能大,在 相同时让 Alice 尽可能小。
两人都采取最优策略,求最终的
正解
思路
朴素做法是 DFS 枚举所有根到叶的路径,在叶子上得到一对
关键观察一:偏好可以统一成同一个二元组。 把结局记作有序对
- Alice 想要
越小越好, 相同则 越大(即 越小)越好 —— 她追求 的字典序最小; - Bob 想要
越大越好, 相同则 越小(即 越大)越好 —— 他追求 的字典序最大。
两人的方向恰好相反,于是这题就是一个标准的极小极大博弈:同一个评价函数,
一方取其最小、一方取其最大。评价函数的两个关键字顺序不能颠倒——先比
关键观察二:轮到谁只由深度决定,且结点本身是常数。 每次移动恰好往下走一层,
所以轮到谁取结点
由于取走
状态定义。 记
转移。 设
是叶子:谁取谁得。偶数深度 ,奇数深度 。 - 偶数深度(Alice 取走
,接着由 Bob 挑儿子):Bob 要最大化 的字典序,取 ,于是 。 - 奇数深度(Bob 取走
,接着由 Alice 挑儿子):Alice 要最小化同一个二元组, 取 ,于是 。
为什么这样合并是自洽的? 两人实际比较的是最终总量,而已经取定的石子
(根到
答案即
举题面样例验证:
, , (叶子上由 Alice 取得)。 - 结点
在奇数深度:Bob 取 ,由 Alice 挑唯一儿子 4, 故 。 - 结点
在奇数深度:Bob 取 ,由 Alice 在 中按 取字典序最小者。两者第一关键字同为 ,第二关键字 ,故选 5, 得 。 - 根
在偶数深度:Alice 取 ,由 Bob 在 中按 取字典序最大者。第一关键字同为 ,第二关键字 ,故选 3。
最终 7 16,与样例一致。
代码
#!/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 06:36
# update_at: 2026-10-08 06:36
import sys
type Adj = list[list[int]] # 邻接表:adj[u] 存 u 的全部邻居(父点 + 儿子)
type Pair = tuple[int, int] # 评价二元组 (Bob, -Alice):定义只此一处;Alice 取最小、Bob 取最大
def build_order(root: int, adj: Adj) -> tuple[list[int], list[int]]:
"""返回 (BFS 序, 每个点的父结点)。迭代实现,链长 1e5 也不会爆栈。
order 自己当队列:边遍历边追加队尾,于是父结点恒排在儿子之前;
只跳过连回父结点的边(树不会有别的重边)。
"""
par = [0] * len(adj)
order = [root]
for u in order:
for v in adj[u]:
if v != par[u]:
par[v] = u
order.append(v)
return order, par
def play(root: int, order: list[int], par: list[int], adj: Adj, num: list[int]) -> Pair:
"""在树上做极小极大 DP,返回 (Alice 总得分, Bob 总得分)。
谁取结点 u 只由深度决定:根为第 0 层,偶数层 Alice 取、奇数层 Bob 取;
取完 u 之后由对手从 u 的儿子里挑一个继续。
"""
dep = [0] * len(adj) # 到根的深度
for u in order[1:]:
dep[u] = dep[par[u]] + 1
alice = [0] * len(adj) # 子树内 Alice 的得分(双方均最优)
bob = [0] * len(adj) # 子树内 Bob 的得分(双方均最优)
def pair(v: int) -> Pair:
"""结点 v 的评价二元组,供 max/min 择优使用。"""
return bob[v], -alice[v]
for u in reversed(order): # 逆 BFS 序:儿子先算完
kids = [v for v in adj[u] if v != par[u]]
if not kids: # 叶子:谁取走谁得 num[u]
if dep[u] % 2 == 0:
alice[u] = num[u]
else:
bob[u] = num[u]
elif dep[u] % 2 == 0:
# Alice 取走 num[u],随后 Bob 挑儿子:让自己多、进而让 Alice 少
v = max(kids, key=pair)
alice[u], bob[u] = num[u] + alice[v], bob[v]
else:
# Bob 取走 num[u],随后 Alice 挑儿子:让 Bob 少、进而让自己多
v = min(kids, key=pair)
alice[u], bob[u] = alice[v], num[u] + bob[v]
return alice[root], bob[root]
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
num = [0] + [next(data) for _ in range(n)]
adj: Adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1) # 入度:有向树上只有根入度为 0,它就是 Alice 先取的那一点
for _ in range(n - 1):
u, v = next(data), next(data)
adj[u].append(v)
adj[v].append(u)
indeg[v] += 1
root = indeg.index(0, 1) # 从下标 1 开始找第一个入度为 0 的点
order, par = build_order(root, adj)
print(*play(root, order, par, adj, num))
if __name__ == "__main__":
solve()/**
* 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 06:36
* update_at: 2026-10-08 06:36
*/
// 树形博弈 DP(minimax + 双关键字字典序)
// 结点 u 由谁取,只看它到根的深度奇偶:偶数层(根为第 0 层)Alice 取,
// 奇数层 Bob 取;取完 u 之后由**对手**在 u 的儿子里挑一个继续。
// 记 f(u) = (bob[u], alice[u]) 为从 u 取到叶子这一段里两人的得分。
// 偶数层 u:Alice 取 num[u],Bob 挑儿子 v* = argmax (bob[v], -alice[v])
// (先让自己多,再让 Alice 少)→ alice[u]=num[u]+alice[v*], bob[u]=bob[v*]
// 奇数层 u:Bob 取 num[u],Alice 挑儿子 v* = argmin (bob[v], -alice[v])
// (先让 Bob 少,再让自己多)→ bob[u]=num[u]+bob[v*], alice[u]=alice[v*]
// num[u] 对 u 的所有儿子分支是同一个常数,故选择只由儿子的 f 决定,可自底向上合并。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXM = 200005; // 无向存边,最多 2*(n-1) 条
typedef long long ll;
ll n;
ll num[MAXN]; // 第 i 堆的石子数
int head[MAXN]; // 链式前向星
int to[MAXM], nxt[MAXM], ecnt; // 无向边存储
int indeg[MAXN]; // 入度:有向树上入度为 0 的结点就是根(它就是被 Alice 先取的那个点)
int par[MAXN]; // BFS 的父结点
int dep[MAXN]; // 到根的深度,根的深度为 0
int order[MAXN]; // BFS 序:父亲一定排在儿子前面
int ocnt;
ll alice[MAXN]; // 子树内 Alice 在双方最优策略下的得分
ll bob[MAXN]; // 子树内 Bob 在双方最优策略下的得分
// 加一条无向边(题面给的是 u 是 v 的父亲,但无向遍历对方向更宽容)
void add_edge(int u, int v) {
ecnt++;
to[ecnt] = v;
nxt[ecnt] = head[u];
head[u] = ecnt;
}
void read_input() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> num[i];
}
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
indeg[v]++;
}
}
void solve() {
// 迭代 BFS 定序:n = 1e5 的链不许递归,队列就是 order 数组本身
int root = 1;
for (int i = 1; i <= n; i++) {
if (indeg[i] == 0) {
root = i;
break;
}
}
ocnt = 1;
order[1] = root;
par[root] = 0;
dep[root] = 0;
for (int i = 1; i <= ocnt; i++) {
int u = order[i];
for (int e = head[u]; e != 0; e = nxt[e]) {
int v = to[e];
if (v == par[u]) continue; // 不回走父结点
par[v] = u;
dep[v] = dep[u] + 1;
ocnt++;
order[ocnt] = v;
}
}
// 逆 BFS 序做 DP:儿子先算完
for (int i = ocnt; i >= 1; i--) {
int u = order[i];
int best = 0;
for (int e = head[u]; e != 0; e = nxt[e]) {
int v = to[e];
if (v == par[u]) continue;
if (best == 0) {
best = v;
continue;
}
if (dep[u] % 2 == 0) {
// 这一层的选择权在 Bob:先 bob 大,再 alice 小
if (bob[v] > bob[best] || (bob[v] == bob[best] && alice[v] < alice[best]))
best = v;
} else {
// 这一层的选择权在 Alice:先 bob 小,再 alice 大
if (bob[v] < bob[best] || (bob[v] == bob[best] && alice[v] > alice[best]))
best = v;
}
}
if (dep[u] % 2 == 0) {
// Alice 取走 num[u];best == 0 说明 u 是叶子,对手没有可选的儿子
alice[u] = num[u] + (best == 0 ? 0 : alice[best]);
bob[u] = (best == 0 ? 0 : bob[best]);
} else {
bob[u] = num[u] + (best == 0 ? 0 : bob[best]);
alice[u] = (best == 0 ? 0 : alice[best]);
}
}
cout << alice[root] << " " << bob[root] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
时间
实测(本机 CPython 3.14,含读入):
总结
本题是"极小极大博弈 + 树形 DP"的入门题。两个要点:
- 偏好归一化:两个人的目标不是两个独立的标量,而是同一个二元组
的字典序——一方取 、一方取 。把"先……再……" 翻译成字典序的关键字顺序,是这类题的通用套路;顺序写反(先比 )会在 全体取平的测点上出错。 - 决策权归属由深度决定:谁取结点
只由深度奇偶决定,而 是常数, 于是"在 处选哪个儿子"退化成只依赖儿子子树的博弈结果,可以自底向上合并。
实现上两条易错点:一是建树时只按题给方向连父
数据来源说明:本题测试数据来自素材源
new_ROJ/problems/1818/data/, 由该目录下的data.py用随机/构造方式(std.cpp作答案生成器)自造, 分 10 个点覆盖边界、星形、链、随机树、完全二叉树等形态, 手算点已与题面样例及预期值逐字节比对通过;题面本身为网络重建版本, 与官方原题的出题意图可能存在偏差,此处结论仅以题面与自造数据为准。