树上取石子

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

把双方偏好统一成二元组 (Bob, -Alice) 的字典序,在树上按深度奇偶交替做极小极大 DP,自底向上 O(n) 合并子树。

OJ: roj

题目 ID: 1818

难度:普及+/提高-

标签:树形DP博弈论极小极大搜索python

创建: 2026-10-08 06:36

更新: 2026-10-08 06:36

形式化题目

给定一棵 nn 个结点的有向树,结点 ii 上有 num[i]num[i] 个石子。给出 n−1n-1 条 "uu 是 vv 的父亲"的边(保证构成一棵以入度为 00 的结点为根的有向树)。 游戏从根开始:Alice 先取走根上的石子,此后轮流进行,谁取走了结点 uu 的石子, 就由对手从 uu 的儿子中挑一个继续取,直到走到叶子(没有儿子的结点)时游戏结束。

设结束时 Alice 共得 SAS_A、Bob 共得 SBS_B,两人的偏好是:

  • Alice:先让 SBS_B 尽可能小,在 SBS_B 相同时让自己 SAS_A 尽可能大;
  • Bob:先让自己 SBS_B 尽可能大,在 SBS_B 相同时让 Alice SAS_A 尽可能小。

两人都采取最优策略,求最终的 (SA,SB)(S_A, S_B)。输出一行两个整数,先 Alice 后 Bob。

正解

思路

朴素做法是 DFS 枚举所有根到叶的路径,在叶子上得到一对 (SA,SB)(S_A, S_B), 再回溯做决策。满二叉树下路径数是 O(2n)O(2^n),n⩽105n \leqslant 10^5 时必然超时。 瓶颈在于没有利用"从某个结点往下的子博弈是独立子问题"这一点。

关键观察一:偏好可以统一成同一个二元组。 把结局记作有序对 (SB, −SA)(S_B,\,-S_A)。由题面偏好直接读出:

  • Alice 想要 SBS_B 越小越好,SBS_B 相同则 SAS_A 越大(即 −SA-S_A 越小)越好 —— 她追求 (SB, −SA)(S_B,\,-S_A) 的字典序最小;
  • Bob 想要 SBS_B 越大越好,SBS_B 相同则 SAS_A 越小(即 −SA-S_A 越大)越好 —— 他追求 (SB, −SA)(S_B,\,-S_A) 的字典序最大。

两人的方向恰好相反,于是这题就是一个标准的极小极大博弈:同一个评价函数, 一方取其最小、一方取其最大。评价函数的两个关键字顺序不能颠倒——先比 SBS_B, 相等才比 SAS_A,这正是题面"在……的前提下"的含义。

关键观察二:轮到谁只由深度决定,且结点本身是常数。 每次移动恰好往下走一层, 所以轮到谁取结点 uu,只取决于 uu 到根的深度。把根的深度记作 00, 则偶数深度由 Alice 取、奇数深度由 Bob 取。

由于取走 uu 的必然是某个确定的人,num[u]num[u] 一定加到那个人的得分上; 而 uu 的儿子分支的收益与 num[u]num[u] 无关。所以在 uu 处做选择时, num[u]num[u] 是一个对所有分支相同的常数,决策完全由儿子子树的博弈结果决定—— 子问题可以自底向上独立求解。

状态定义。 记 f(u)=(bob[u], alice[u])f(u)=(bob[u],\,alice[u]),表示"从取走 uu 开始、直到走到叶子结束" 这段子博弈中,Bob 与 Alice 各自的总得分。

转移。 设 uu 的儿子集合为 C(u)C(u):

  • uu 是叶子:谁取谁得。偶数深度 f(u)=(0, num[u])f(u)=(0,\,num[u]),奇数深度 f(u)=(num[u], 0)f(u)=(num[u],\,0)。
  • 偶数深度(Alice 取走 num[u]num[u],接着由 Bob 挑儿子):Bob 要最大化 (bob[v], −alice[v])(bob[v],\,-alice[v]) 的字典序,取 v\*=arg⁡max⁡v∈C(u)(bob[v], −alice[v])v^\*=\arg\max_{v\in C(u)}(bob[v],\,-alice[v]),于是 alice[u]=num[u]+alice[v\*], bob[u]=bob[v\*]alice[u]=num[u]+alice[v^\*],\ bob[u]=bob[v^\*]。
  • 奇数深度(Bob 取走 num[u]num[u],接着由 Alice 挑儿子):Alice 要最小化同一个二元组, 取 v\*=arg⁡min⁡v∈C(u)(bob[v], −alice[v])v^\*=\arg\min_{v\in C(u)}(bob[v],\,-alice[v]),于是 bob[u]=num[u]+bob[v\*], alice[u]=alice[v\*]bob[u]=num[u]+bob[v^\*],\ alice[u]=alice[v^\*]。

为什么这样合并是自洽的? 两人实际比较的是最终总量,而已经取定的石子 (根到 uu 的路径上的全部石子)在每个候选分支里都是同一个常数。给两个候选结局 同时加上同一个常数,不改变二元组 (SB, −SA)(S_B,\,-S_A) 的字典序比较结果, 所以"在 uu 处按子树结果择优"与"按最终总量择优"完全等价。

答案即 f(root)f(root),输出 alice[root]alice[root] 与 bob[root]bob[root]。

举题面样例验证:num[1..6]=[4,16,16,5,3,1]num[1..6]=[4,16,16,5,3,1],树为 1→2, 2→4, 1→3, 3→5, 3→61\to2,\ 2\to4,\ 1\to3,\ 3\to5,\ 3\to6。 深度 0 是根(Alice),深度 1 的 2,32,3 是 Bob,深度 2 的叶子 4,5,64,5,6 又轮到 Alice。

  • f(4)=(bob,alice)=(0,5)f(4)=(bob,alice)=(0,5),f(5)=(0,3)f(5)=(0,3),f(6)=(0,1)f(6)=(0,1)(叶子上由 Alice 取得)。
  • 结点 22 在奇数深度:Bob 取 num[2]=16num[2]=16,由 Alice 挑唯一儿子 4, 故 f(2)=(16, 0+5)=(16,5)f(2)=(16,\,0+5)=(16,5)。
  • 结点 33 在奇数深度:Bob 取 num[3]=16num[3]=16,由 Alice 在 5,65,6 中按 (bob,−alice)(bob,-alice) 取字典序最小者。两者第一关键字同为 00,第二关键字 −3<−1-3 < -1,故选 5, 得 f(3)=(16, 0+3)=(16,3)f(3)=(16,\,0+3)=(16,3)。
  • 根 11 在偶数深度:Alice 取 num[1]=4num[1]=4,由 Bob 在 2,32,3 中按 (bob,−alice)(bob,-alice) 取字典序最大者。第一关键字同为 1616,第二关键字 −3>−5-3 > -5,故选 3。

最终 alice[1]=4+3=7alice[1]=4+3=7,bob[1]=0+16=16bob[1]=0+16=16,输出 7 16,与样例一致。

代码

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 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()
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-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;
}

复杂度

时间 O(n)O(n):每个结点恰好入列一次,DP 时每条父子边只被扫一遍。 空间 O(n)O(n):邻接表(2(n−1)2(n-1) 条无向边)、par/dep/orderpar/dep/order、num/alice/bobnum/alice/bob 各 O(n)O(n)。

实测(本机 CPython 3.14,含读入):n=105n=10^5 的随机树约 0.070.07 s, n=105n=10^5 完全二叉树(10510^5 个形态各异的小子树)约 0.070.07 s,n=105n=10^5 链约 0.080.08 s; C++ 版在同一批数据上单点不足 2020 ms,11 s 时限下余量很大。

总结

本题是"极小极大博弈 + 树形 DP"的入门题。两个要点:

  1. 偏好归一化:两个人的目标不是两个独立的标量,而是同一个二元组 (SB, −SA)(S_B,\,-S_A) 的字典序——一方取 min⁡\min、一方取 max⁡\max。把"先……再……" 翻译成字典序的关键字顺序,是这类题的通用套路;顺序写反(先比 SAS_A)会在 全体取平的测点上出错。
  2. 决策权归属由深度决定:谁取结点 uu 只由深度奇偶决定,而 num[u]num[u] 是常数, 于是"在 uu 处选哪个儿子"退化成只依赖儿子子树的博弈结果,可以自底向上合并。

实现上两条易错点:一是建树时只按题给方向连父 →\to 子的有向边、从根 1 单向 遍历,若误建双向边会绕回父亲导致死循环(本解建无向边但跳过父结点,效果相同, 且不依赖"根一定是 1",而是取入度为 00 的点);二是第二关键字的方向极易写反 (Alice 挑儿子时取 alicealice 更大者,Bob 挑儿子时取 alicealice 更小者)。 n=105n=10^5 的链会打穿递归深度,故两边都用迭代 BFS 定序、逆序 DP。

数据来源说明:本题测试数据来自素材源 new_ROJ/problems/1818/data/, 由该目录下的 data.py 用随机/构造方式(std.cpp 作答案生成器)自造, 分 10 个点覆盖 n=1n=1 边界、星形、链、随机树、完全二叉树等形态, 手算点已与题面样例及预期值逐字节比对通过;题面本身为网络重建版本, 与官方原题的出题意图可能存在偏差,此处结论仅以题面与自造数据为准。