NekoNowcoder

Appearance

树上博弈 - 题解 ​

标签与难度 ​

标签: 树形DP, 博弈论, 极小化极大思想, DFS, 游戏理论 难度: 1800

题目大意喵~ ​

各位Master，大家好呀，喵~ ฅ'ω'ฅ

这道题是关于一棵有根树的博弈游戏哦！我们有一棵 nn 个节点的树，1号节点是树根。除了根节点，其他每个节点 ii 上都有 cic_i 枚金币。

游戏是这样的：

  1. 一个棋子开始时放在根节点（1号节点）。
  2. Alice 和 Bob 轮流移动棋子，Alice 先手。
  3. 轮到某个玩家时，TA必须把棋子从当前节点 xx 移动到它的任意一个子孙节点 yy。
  4. 移动棋子的玩家会获得节点 yy 上的所有金币。
  5. 当棋子被移动到一个叶子节点（没有子节点的节点）时，游戏就结束啦，因为无法再进行任何移动了。

Alice 的目标是让自己的金币数减去 Bob 的金币数（也就是 a−ba-b）尽可能大。而 Bob 的目标正好相反，他想让这个差值尽可能小。他们两个都超级聪明，每一步都会选择最优的策略。

我们的任务就是，在他们都采取最优策略的情况下，预测游戏结束时 a−ba-b 的最终值是多少，的说！

解题思路分析 ​

喵哈~ 看到这种 Alice 和 Bob 轮流操作，并且都想让自己利益最大化（或者让对方利益最小化）的问题，我们聪明的直觉就应该告诉我们，这很可能是一个博弈论问题，而且可以用极小化极大思想 (Minimax) 来解决，呐！

因为游戏是在一棵树上进行的，所以我们可以很自然地联想到树形动态规划 (Tree DP)。

1. 定义DP状态 ​

首先，我们要定义一个清晰的 DP 状态。对于树上的任意一个节点 u，当轮到某位玩家，且棋子正好在节点 u 上时，这个局面会有一个“价值”。这个价值就是从当前局面开始，当前玩家能获得的最大领先分数（也就是自己得分 - 对手得分）。

所以，我们定义 dp[u]dp[u] 为：棋子在节点 u，轮到当前玩家操作，游戏结束后该玩家能获得的最大 (自己的总金币 - 对手的总金币) 差值。

我们的最终目标就是计算出 dp[1]dp[1]，因为游戏是从根节点1开始，并且 Alice 先手。

2. 寻找状态转移方程 ​

要计算 dp[u]dp[u]，我们就得站在节点 u 的玩家（我们叫他 P 好了）的角度思考。P 有哪些选择呢？根据规则，P 可以把棋子移动到 u 的任意一个子孙节点 w。

假设 P 选择了移动到子孙节点 w。会发生什么呢？

  1. P 立刻获得 w 节点上的 cwc_w 个金币。
  2. 棋子移动到了 w，现在轮到对手（我们叫他 O）操作了。
  3. 根据我们的 DP 定义，从 w 节点开始，O 作为当前玩家，能取得的最大分差是 dp[w]dp[w]。

所以，如果 P 选择移动到 w，那么 P 的净收益就是：自己这次拿到的 cwc_w 减去 对手接下来能从 w 开始取得的领先优势 dp[w]dp[w]。也就是 cw−dp[w]c_w - dp[w]。

因为 P 是个聪明的玩家，TA 会在所有可能的子孙节点 w 中，选择一个能使自己的净收益 cw−dp[w]c_w - dp[w] 最大的 w。

于是，我们得到了初步的状态转移方程：

dp[u]=max⁡w∈descendants of u{cw−dp[w]}dp[u] = \max_{w \in \text{descendants of } u} \{ c_w - dp[w] \}

3. 优化状态转移 ​

这个方程看起来很美，但是有个问题喵~ 对于每个节点 u，我们都需要遍历它的所有子孙节点，如果树的形态比较极端（比如一条链），那计算一个节点的 DP 值可能需要 O(N)O(N) 的时间，总时间复杂度会达到 O(N2)O(N^2)，对于 NN 很大的情况，肯定会超时的说。

我们需要优化它！我们来观察一下 u 的子孙节点集合。u 的所有子孙节点，可以被划分为 u 的每个直接孩子 v 以及 v 的子孙们。

所以，我们可以把上面的 max 运算拆开：

dp[u]=max⁡v∈children of u(max⁡({cv−dp[v]}∪{cw−dp[w]∣w∈descendants of v}))dp[u] = \max_{v \in \text{children of } u} \left( \max \left( \{c_v - dp[v]\} \cup \{ c_w - dp[w] \mid w \in \text{descendants of } v \} \right) \right)

这个式子看起来更复杂了，别怕！我们仔细看看括号里的部分。 {cw−dp[w]∣w∈descendants of v}\{ c_w - dp[w] \mid w \in \text{descendants of } v \} 这一坨，它的最大值是什么？ 喵！这不就是 dp[v]dp[v] 的定义嘛！

dp[v]=max⁡w∈descendants of v{cw−dp[w]}dp[v] = \max_{w \in \text{descendants of } v} \{ c_w - dp[w] \}

所以，对于 u 的每一个孩子 v，玩家在 u 能做出的和 v 的子树相关的决策，其实只有两种：

  1. 直接跳到 v，收益是 cv−dp[v]c_v - dp[v]。
  2. 跳到 v 的某个子孙 w，能获得的最大收益就是 dp[v]dp[v]。

玩家会选择这两种中更好的那一个，所以从 v 这条分支能获得的最大收益是 max⁡(cv−dp[v],dp[v])\max(c_v - dp[v], dp[v])。

最后，玩家 P 在节点 u 时，会考察所有孩子 v，并选择能提供最大收益的那条分支。于是，我们得到了最终的、高效的状态转移方程：

dp[u]=max⁡v∈children of u{max⁡(cv−dp[v],dp[v])}dp[u] = \max_{v \in \text{children of } u} \{ \max(c_v - dp[v], dp[v]) \}

对于叶子节点 l，因为它没有孩子，所以 dp[l]dp[l] 就是一个空集合里的最大值。在博弈中，如果一个状态没有后继状态，它的价值就是0。所以我们的 base case 是 dp[leaf]=0dp[\text{leaf}] = 0。

4. 计算顺序 ​

为了计算 dp[u]dp[u]，我们需要先知道它所有孩子 v 的 dp[v]dp[v] 值。这告诉我们，计算应该从叶子节点开始，一层一层向上，直到根节点。这种 "子问题解决后，再解决父问题" 的顺序，最适合用 DFS (深度优先搜索) 的后序遍历来实现啦！

我们从根节点开始DFS，先递归进入所有子节点，当子节点的 dp 值全部计算完毕返回后，再利用它们来计算当前节点的 dp 值。太完美了，喵~

代码实现 ​

下面是我为大家准备的一份干净整洁、注释详细的 C++ 代码实现，希望能帮到大家哦！

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

// 为了防止数值溢出，使用 long long 是个好习惯喵~
using ll = long long;

// n: 节点数量
// adj: 邻接表，adj[u] 存储 u 的所有孩子节点
// coins: 存储每个节点的金币数量
int n;
std::vector<std::vector<int>> adj;
std::vector<ll> coins;
// dp[u] 存储棋子在 u，当前玩家行动能获得的最大分差
std::vector<ll> dp;

// 使用深度优先搜索来计算DP值
void dfs(int u) {
    // 如果当前节点是叶子节点，它没有孩子，无法移动
    // 根据我们的DP定义，无法行动的状态价值为0
    if (adj[u].empty()) {
        dp[u] = 0;
        return;
    }

    // dp[u] 的初始值设为-∞，因为我们要取最大值
    // 这里用一个非常小的负数代替
    ll max_gain = -2e18; // 一个足够小的数

    // 遍历 u 的所有孩子 v
    for (int v : adj[u]) {
        // 先递归计算子问题 dp[v]
        dfs(v);

        // 对于孩子 v，玩家可以选择跳到 v，或者跳到 v 的子孙
        // 收益分别是 coins[v] - dp[v] 和 dp[v]
        ll gain_from_v_subtree = std::max(coins[v] - dp[v], dp[v]);

        // 更新从 u 出发能获得的最大收益
        if (gain_from_v_subtree > max_gain) {
            max_gain = gain_from_v_subtree;
        }
    }

    // 最终 dp[u] 的值就是所有选择中的最优解
    dp[u] = max_gain;
}

void solve() {
    std::cin >> n;

    // 初始化/清空数据结构
    // 节点编号为 1 到 n，所以我们开 n+1 大小的数组
    adj.assign(n + 1, std::vector<int>());
    coins.assign(n + 1, 0);
    dp.assign(n + 1, 0);

    // 读取金币信息，注意根节点1没有金币，所以从2开始
    for (int i = 2; i <= n; ++i) {
        std::cin >> coins[i];
    }

    // 读取父节点信息，构建树的邻接表（从父节点到子节点）
    // 节点i的父节点是p
    for (int i = 2; i <= n; ++i) {
        int p;
        std::cin >> p;
        adj[p].push_back(i);
    }

    // 从根节点1开始DFS
    dfs(1);

    // 最终答案就是 dp[1]
    std::cout << dp[1] << std::endl;
}

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(N)O(N) 我们的 dfs 函数会访问每个节点和每条边恰好一次。在每个节点内部，我们遍历它的孩子节点。由于所有节点的度数之和等于边数（N−1N-1），所以总的计算量是和节点数 NN 成正比的。因此，时间复杂度是线性的 O(N)O(N)，非常高效！

  • 空间复杂度: O(N)O(N) 我们需要用邻接表 adj 来存储树的结构，这需要 O(N)O(N) 的空间。coins 和 dp 数组也需要 O(N)O(N) 的空间。此外，DFS 的递归调用栈在最坏的情况下（树是一条长链）深度可能达到 NN，也需要 O(N)O(N) 的空间。所以总的空间复杂度是 O(N)O(N)。

知识点总结 ​

这道题真是一次愉快的思维体操呢，喵~ 它融合了好几个重要的知识点：

  1. 博弈论与极小化极大思想: 这是解决这类双人对抗性游戏的核心。理解“我方的最优选择是基于敌方也会做出最优选择”这一前提是关键。
  2. 树形动态规划: 将博弈问题建模在树上，并利用树的递归结构设计 DP 状态和转移方程，是解决树上问题的经典方法。
  3. 问题分解与优化: 从一个看起来复杂的 DP 方程（遍历所有子孙）出发，通过分析问题结构，将其优化为只依赖于直接孩子状态的高效方程，这是算法设计中非常重要的一步。
  4. DFS后序遍历: 这种 "自底向上" 计算 DP 值的方式，天然地契合了 DFS 的后序遍历过程，使得代码实现非常优雅。

希望这篇题解能帮助各位 Master 理解这道有趣的题目！如果还有问题，随时可以再来问我哦，喵~ 祝大家刷题愉快！