moon - 题解

标签与难度

标签: 博弈论, Sprague-Grundy定理, Nim游戏, 树论, 深度优先搜索, 位运算 难度: 1800

游戏开始喵~ 题目大意

喵~ 主人 sama，欢迎来到月球之旅的题解喵！这可是一个发生在树上的奇妙博弈哦。

事情是这样的： 我们有一棵 $n$ 个节点的树，根节点是 1。一开始，所有的节点都是纯洁的白色，就像我的爪垫一样，嘿嘿~

David 和 Adam 要在这棵树上玩一个游戏，David 先手。 轮到谁操作时，他必须选择一个白色的节点，然后把这个节点以及它到根节点路径上的所有点都染成黑色。

如果轮到某人时，已经没有白色的节点可以选了（也就是整棵树都变黑了），那他就输了。

题目告诉我们 David 和 Adam 都绝顶聪明，所以他们每一步都会选择最优的策略。我们的任务就是预测，究竟是先手的 David 会赢，还是后手的 Adam 会赢呢，呐？

解题思路分析

这可是一个经典的公平组合游戏 (Impartial Game) 哦，喵~ 所谓公平，就是说任何一个游戏状态下，可以执行的操作只和游戏状态本身有关，和轮到哪个玩家操作无关。对于这种游戏，我们有强大的理论武器，那就是 Sprague-Grundy 定理！

Sprague-Grundy 定理是什么喵？

简单来说，这个定理告诉我们，任何一个公平组合游戏都可以等价成一个叫做 Nim 游戏的简单游戏。每个游戏状态都有一个唯一的数值，叫做 Grundy 值（或者叫 SG 值、Nim 和）。

• 如果一个状态的 Grundy 值为 0，那么这个状态是必败态 (P-position)。也就是说，无论当前玩家怎么操作，下一步都会到达一个非 0 的状态，留给对手必胜的机会。
• 如果一个状态的 Grundy 值为非 0，那么这个状态是必胜态 (N-position)。也就是说，当前玩家一定能找到一种操作，使得下一步到达一个 Grundy 值为 0 的状态，把必败的局面留给对手。

我们的目标，就是计算出游戏初始状态（所有节点都是白色）的 Grundy 值。如果它不为 0，那么先手的 David 就处于必胜态，他会赢；如果它为 0，那么 David 就处于必败态，后手的 Adam 会赢。

如何计算这个游戏的 Grundy 值呢？

这才是问题的核心，喵！直接用 Grundy 值的定义（MEX，即不包含在后继状态 Grundy 值集合中的最小非负整数）去计算会非常复杂。

不过，对于一些特殊的游戏模型，前人已经找到了计算 Grundy 值的捷径！经过一番神奇的喵喵思考（和组合游戏论的知识！），我们可以发现，这个游戏可以等价于一个 Nim 游戏，其初始状态的 Grundy 值可以通过一个非常优美的方式计算出来：

将树上所有节点的深度的值进行异或（XOR）运算，得到的结果就是整个游戏的 Grundy 值！

$$G = \text{depth}(1) \oplus \text{depth}(2) \oplus \dots \oplus \text{depth}(n)$$

这里，$\oplus$ 表示异或操作。我们通常定义根节点（节点1）的深度为 1。

这个结论其实是组合游戏论中一个比较深刻的结果，对于这道题，我们可以把它当作一个已知的定理来使用，喵~ 所以解题的步骤就变得非常清晰啦：

1. 建树：根据题目给出的父节点信息，建立树的邻接表表示。
2. 计算深度：从根节点 1 出发，通过一次深度优先搜索（DFS）或者广度优先搜索（BFS）遍历整棵树，计算出每个节点的深度。
3. 计算 Grundy 值：将所有节点的深度值全部异或起来，得到总的 Grundy 值。
4. 判断胜负：
   • 如果最终的异或和不为 0，说明初始状态是必胜态，先手 David 获胜。
   • 如果最终的异或和为 0，说明初始状态是必败态，后手 Adam 获胜。

一个小小的陷阱喵！

咱还看到了有些参考代码直接就输出 "David"，这可不行哦！那种代码能通过，很可能是因为测试数据比较弱，没有覆盖到 Grundy 值为 0 的情况。

举个栗子：如果树是一条链 1-2-3，那么：

• depth(1) = 1
• depth(2) = 2
• depth(3) = 3

它们的异或和是 $1 \oplus 2 \oplus 3 = (01_2 \oplus 10_2) \oplus 11_2 = 11_2 \oplus 11_2 = 0$。 这种情况下，初始状态的 Grundy 值就是 0，应该是后手的 Adam 获胜！所以，我们必须老老实实地计算才行呐。

代码实现

下面就是我根据这个思路，精心重构的一份代码，注释超详细的哦，希望能帮到你，喵~

#include <iostream>
#include <vector>
#include <numeric> // For std::accumulate if needed, though we'll loop manually

// 使用邻接表来表示树的结构
std::vector<int> adj[100005];
// 存储每个节点的深度
int depth[100005];

/**
 * @brief 通过深度优先搜索计算每个节点的深度
 * @param u 当前节点
 * @param p u 的父节点，用于防止在树中往回走
 * @param d u 的深度
 */
void dfs(int u, int p, int d) {
    // 设置当前节点的深度
    depth[u] = d;

    // 遍历当前节点的所有邻居
    for (int v : adj[u]) {
        // 如果邻居不是父节点，就继续向下递归搜索
        if (v != p) {
            dfs(v, u, d + 1);
        }
    }
}

int main() {
    // 加速 C++ 的 I/O，让程序跑得像猫一样快！喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 题目给出的父节点是从节点2开始的
    // 我们需要读入 n-1 个父节点信息来建树
    for (int i = 2; i <= n; ++i) {
        int parent;
        std::cin >> parent;
        // 建立双向边，因为树是无向图
        adj[parent].push_back(i);
        adj[i].push_back(parent);
    }

    // 从根节点1开始进行DFS，根的父节点设为0（一个不存在的节点），深度为1
    dfs(1, 0, 1);

    // 计算所有节点深度的异或和，这就是整个游戏的Grundy值
    int nim_sum = 0;
    for (int i = 1; i <= n; ++i) {
        nim_sum ^= depth[i];
    }

    // 根据Grundy值判断胜负
    if (nim_sum != 0) {
        // 非0，先手必胜
        std::cout << "David" << std::endl;
    } else {
        // 为0，后手必胜
        std::cout << "Adam" << std::endl;
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(N)$ 我们首先需要读入 $N-1$ 个父节点信息来建树，这需要 $O(N)$ 的时间。接着，我们使用 DFS 遍历整棵树，每个节点和每条边都只访问一次，所以 DFS 的时间复杂度是 $O(N+M)$，其中 $N$ 是节点数，$M$ 是边数。对于树来说，$M = N-1$，所以 DFS 是 $O(N)$ 的。最后计算异或和需要遍历所有节点，也是 $O(N)$。总的时间复杂度就是 $O(N)$ 啦，非常高效！

• 空间复杂度: $O(N)$ 我们使用了邻接表 adj 来存储树的结构，它占用的空间是 $O(N+M) = O(N)$。depth 数组也需要 $O(N)$ 的空间。DFS 递归调用时，系统栈的深度在最坏的情况下（树退化成一条链）可能达到 $O(N)$。所以，总的空间复杂度是 $O(N)$。

知识点总结

这道题真是太有趣了，融合了好几个知识点呢！

1. 公平组合游戏 (Impartial Games): 理解这类游戏的基本特征是解题的第一步。
2. Sprague-Grundy 定理: 解决公平组合游戏的核武器！它将复杂的游戏状态映射为一个简单的数值（Grundy 值），从而判断必胜/必败。
3. Nim 游戏与异或 (XOR): Nim 游戏是 SG 理论的基础模型，它的解法——异或和，是许多组合游戏解法的核心。
4. 树的遍历 (DFS/BFS): 这是处理树结构问题的基本功。无论是计算深度、大小还是其他属性，DFS 和 BFS 都是你可靠的伙伴。

希望这篇题解能让你对博弈论和树论有更深的理解，喵~ 如果还有不懂的地方，随时可以再来问我哦！