E. Demiurges Play Again - 题解

比赛与标签

比赛: Codeforces Round 300 标签: dfs and similar, dp, math, trees 难度: *2200

题目大意喵~

主人，这道题是关于一个在树上进行的博弈游戏哦！

是这样子的：我们有一棵有 n 个节点的有根树（根是节点1），其中有 m 个叶子节点。现在，我们需要把数字 1 到 m 不重不漏地填到这 m 个叶子节点里。

游戏规则是：

一个棋子开始放在根节点。
两个玩家轮流移动棋子，每次只能从当前节点移动到它的一个子节点。
当棋子到达一个叶子节点时，游戏结束，游戏的结果就是那个叶子节点上的数字。

玩家一（先手）的目标是让游戏结果尽可能大，而玩家二（后手）的目标是让结果尽可能小。他们都超级聪明，会选择最优的策略。

在游戏开始前，有两位神（Shambambukli 和 Mazukta）可以任意安排叶子节点上的数字。

Shambambukli 想让最终的游戏结果尽可能大。
Mazukta 想让最终的游戏结果尽可能小。

我们的任务就是，分别计算出在 Shambambukli 和 Mazukta 的安排下，最终的游戏结果会是多少。

博弈论与树形DP的奇妙相遇~

这道题融合了博弈论和树形DP，看起来很复杂，但只要理清思路，就会变得清晰起来，喵~

首先，我们来分析一下玩家的策略。棋子从根节点（深度为0）开始，玩家一移动。然后到深度为1的节点，玩家二移动。接着深度为2，又是玩家一... 规律很明显呐：

在偶数深度的节点上，由玩家一（最大化者） 移动。
在奇数深度的节点上，由玩家二（最小化者） 移动。

这是一个典型的 minimax 问题，非常适合用树形DP来解决。DP的关键在于定义好状态。我们发现，最终结果和叶子上的数字有关，而数字是可以被神任意排列的。所以，DP状态不应该是具体的数值，而应该是为了达到某种目的所需要的叶子数量。

我们分两种情况来讨论，对应两位神的目标。

情况一：Shambambukli (追求最大结果)

Shambambukli 希望最终结果越大越好。假设他想让结果至少为 k，他会怎么做呢？他会把最大的那些数字，也就是 m, m-1, ... 这些，放到玩家一能够确保达到的叶子节点上。

为了让结果最大化，玩家一需要确保无论玩家二怎么走，他总能到达一个被 Shambambukli 标为“高分”的叶子。

于是，我们的DP状态可以定义为： dp1[u]：对于以 u 为根的子树，玩家一为了确保能赢（即走到一个他想去的叶子），最少需要控制多少个叶子节点。

DP的转移逻辑如下（从叶子向根计算）：

当 u 是叶子节点时：这棵子树只有一个叶子，就是它自己。玩家一当然需要控制这1个叶子才能赢。 dp1[u] = 1
当 u 是内部节点，且深度为偶数（玩家一行动）：玩家一可以选择移动到他的任何一个孩子 v。他当然会选择一个对他最有利的路径，也就是完成目标所需叶子数量最少的那个孩子。 dp1[u] = min(dp1[v]) (对于所有 u 的孩子 v)
当 u 是内部节点，且深度为奇数（玩家二行动）：玩家二会想尽办法阻挠玩家一。他会选择一个对玩家一最不利的孩子 v。为了保证在任何情况下都能赢，玩家一必须对玩家二的所有选择都做好准备。也就是说，无论玩家二走到哪个孩子 v_i，玩家一都必须在 v_i 的子树里有能赢的叶子。因为不同孩子的子树所包含的叶子是互不相交的，所以玩家一需要的总叶子数是所有孩子所需叶子数的总和。 dp1[u] = sum(dp1[v]) (对于所有 u 的孩子 v)

计算出 dp1[1] 后，这就是玩家一在整棵树上为了保证胜利最少需要控制的叶子数量。Shambambukli 会把 m 个数字中最大的 dp1[1] 个（即 m, m-1, ..., m - dp1[1] + 1）放在这些叶子上。玩家一会确保走到这些叶子之一，而聪明的玩家二会把他逼到这些叶子中数值最小的那个。所以，最终结果就是 m - dp1[1] + 1。

情况二：Mazukta (追求最小结果)

Mazukta 希望最终结果越小越好。他会把最小的那些数字，也就是 1, 2, ...，放到玩家一无法避开的那些叶子节点上。

我们的DP状态可以定义为： dp2[u]：对于以 u 为根的子树，玩家一最少能被玩家二逼进多少个叶子的集合里。

DP的转移逻辑如下：

当 u 是叶子节点时：只有一个选择，玩家一肯定会到这个叶子。 dp2[u] = 1
当 u 是内部节点，且深度为偶数（玩家一行动）：玩家一想最大化结果，他会试图躲开那些被 Mazukta 标了低分的叶子。Mazukta 为了让他无处可逃，必须在玩家一的所有可选路径上都布下“陷阱”。如果玩家一可以移动到孩子 v_1, v_2, ...，Mazukta 必须保证在 v_1 的子树里有 dp2[v_1] 个陷阱叶子，在 v_2 的子树里有 dp2[v_2] 个... 因为玩家一可以自由选择，Mazukta 必须把所有路径都覆盖到。所以总共需要的陷阱叶子数量是所有孩子所需数量之和。 dp2[u] = sum(dp2[v]) (对于所有 u 的孩子 v)
当 u 是内部节点，且深度为奇数（玩家二行动）：玩家二的目标是把玩家一逼入一个尽可能小的叶子集合中。他会审查所有的孩子 v，然后选择那个能把玩家一限制在最小叶子集合 dp2[v] 的路径。 dp2[u] = min(dp2[v]) (对于所有 u 的孩子 v)

计算出 dp2[1] 后，这就是玩家一在整棵树上最少会被限制住的叶子数量。Mazukta 会把 1, 2, ..., dp2[1] 这些数字放在这个叶子集合上。玩家一虽然被困，但他仍然会从中选择对他最有利的，也就是数值最大的那个。所以，最终结果就是 dp2[1]。

代码实现喵！

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    // 加速输入输出，让程序跑得更快喵~
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // 用邻接表存树的边，因为一开始不知道父子关系
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 如果只有一个节点，它既是根也是叶子，m=1，结果总是1
    if (n == 1) {
        cout << "1 1" << endl;
        return 0;
    }

    // 通过BFS从根节点1开始遍历，确定父子关系和每个节点的深度
    vector<int> depth(n + 1, -1);
    vector<int> parent(n + 1, -1);
    vector<vector<int>> children(n + 1);
    queue<int> q;

    depth[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            // 避免向上走到父节点
            if (v == parent[u]) continue;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            children[u].push_back(v);
            q.push(v);
        }
    }

    // 统计叶子节点的总数 m
    int m = 0;
    for (int i = 1; i <= n; i++) {
        if (children[i].empty())
            m++;
    }

    // 为了进行树形DP，我们需要从深到浅（从叶到根）的顺序处理节点
    vector<int> nodes;
    for (int i = 1; i <= n; i++)
        nodes.push_back(i);
    // 按深度降序排序，就得到了后序遍历的效果
    sort(nodes.begin(), nodes.end(), [&](int a, int b) {
        return depth[a] > depth[b];
    });

    vector<int> dp1(n + 1, 0); // Shambambukli情况的DP数组
    vector<int> dp2(n + 1, 0); // Mazukta情况的DP数组
    const int INF = 1e9;

    // 开始DP！
    for (int u : nodes) {
        // Base Case: 如果是叶子节点
        if (children[u].empty()) {
            dp1[u] = 1;
            dp2[u] = 1;
        } else {
            // 偶数深度，玩家一行动
            if (depth[u] % 2 == 0) {
                // dp1: 玩家一选代价最小的路径
                dp1[u] = INF;
                for (int v : children[u]) {
                    dp1[u] = min(dp1[u], dp1[v]);
                }
                // dp2: Mazukta需要覆盖所有路径
                dp2[u] = 0;
                for (int v : children[u]) {
                    dp2[u] += dp2[v];
                }
            } 
            // 奇数深度，玩家二行动
            else {
                // dp1: 玩家一要应对所有可能，所以是和
                dp1[u] = 0;
                for (int v : children[u]) {
                    dp1[u] += dp1[v];
                }
                // dp2: 玩家二选对玩家一最不利的路径
                dp2[u] = INF;
                for (int v : children[u]) {
                    dp2[u] = min(dp2[u], dp2[v]);
                }
            }
        }
    }

    // 根据我们推导的公式输出最终结果
    cout << m - dp1[1] + 1 << " " << dp2[1] << endl;

    return 0;
}

复杂度分析的说

时间复杂度: O(N log N) 的说。主要瓶颈在于对节点按深度排序。建树（BFS）和树形DP本身都是 O(N) 的。如果用DFS实现后序遍历，可以优化到 O(N) 哟。
空间复杂度: O(N) 的说。用于存储树的邻接表、父子关系、深度以及DP数组，都需要线性的空间。

知识点与总结~ Ciallo～(∠・ω< )⌒☆

这道题真是太有趣啦，把博弈和DP结合得天衣无缝！

核心思想: 解决这种在树上进行的、结果和排列有关的博弈问题，关键是把DP的状态从具体的值转换成为达成目标所需的资源数量（这里是叶子数量）。
双DP数组: 因为有两个独立的目标（Shambambukli最大化 vs Mazukta最小化），所以我们用了两个DP数组 dp1 和 dp2 分别求解，它们的转移逻辑是不同的。
博弈DP的转移: DP的转移规则深刻体现了博弈的思想。
- 当轮到我方（想赢的一方）行动时，我们会选择对自己最有利的选项，通常对应 min（最小代价）或 max（最大收益）。
- 当轮到对方行动时，我们必须为最坏情况做准备，通常对应 sum（覆盖所有选择）或 min/max（对方会把我们逼到最差的境地）。
实现技巧: 对于有根树问题，如果输入只给出了无向边，一个常见的预处理步骤就是通过BFS或DFS从根节点开始遍历，从而确定每个节点的父节点、子节点和深度。

希望这篇题解能帮助主人更好地理解这道题的思路！继续加油，算法的世界还有更多奇妙的冒险等着我们呢，喵~！

E. Demiurges Play Again - 题解 ​

比赛与标签 ​

题目大意喵~ ​

博弈论与树形DP的奇妙相遇~ ​

情况一：Shambambukli (追求最大结果) ​

情况二：Mazukta (追求最小结果) ​

代码实现喵！ ​

复杂度分析的说 ​

知识点与总结~ Ciallo～(∠・ω< )⌒☆ ​