题意理解

我们有一个 DAG，每个节点是黑点或白点，描述了 DFS 程序的执行流程。游戏规则如下：

• 有 $k$ 个独立的 DFS 程序，每个从不同的起点开始
• 玩家轮流选择一个程序执行，直到它再次暂停或结束
• 执行过程中遇到读取布尔值时，当前玩家可以选择 true/false
• 所有程序结束时，轮到谁操作谁就输

这是一个组合博弈问题，需要分析每个起始点的胜负情况，然后计算整体游戏的胜负。

核心思路

关键观察 1：博弈建模

每个 DFS 程序可以看作一个独立的组合游戏，整个游戏是这些独立游戏的 Nim 和（或类似概念）。

我们需要为每个节点 $u$ 计算一个值 $G(u)$，表示从该节点开始的游戏的 Grundy 数（SG 值）。

关键观察 2：DFS 暂停点的博弈意义

程序在每次 dfs(u) 调用前暂停，这意味着：

• 玩家选择执行一个程序时，会从当前暂停点开始执行
• 执行过程中可能遇到多个读取点，玩家可以做出选择
• 执行到下一个暂停点或程序结束时停止

关键观察 3：黑白节点的不同行为

白点 $u$：

• 按顺序遍历出边 $(u,v)$
• 对于每条边，读取布尔值 $g$，如果 $g$ 为真则调用 dfs(v)
• 玩家可以选择是否进入每个子节点

黑点 $u$：

• 按顺序遍历所有出边 $(u,v)$
• 无条件调用 dfs(v)
• 玩家没有选择权，必须进入所有子节点

算法框架

方法一：SG 函数计算

从拓扑序的底部向上计算每个节点的 SG 值：

对于黑点 $u$：

• 必须按顺序访问所有出边对应的子节点
• 这相当于按顺序玩一系列游戏
• $G(u) = G(v_1) \oplus G(v_2) \oplus \cdots \oplus G(v_m)$（顺序游戏的 SG 值）

对于白点 $u$：

• 对于每条出边 $(u,v_i)$，玩家可以选择是否进入
• 这为玩家提供了分支选择
• $G(u)$ 需要计算所有可能选择对应的 SG 值的 mex

方法二：状态表示

由于出边是有序的，我们需要考虑执行路径：

设 $dp[u][i]$ 表示在节点 $u$，已经处理了前 $i$ 条出边时的 SG 值。

状态转移：

• 黑点：$dp[u][i] = dp[u][i-1] \oplus G(v_i)$
• 白点：$dp[u][i] = \text{mex}\{dp[u][i-1], dp[u][i-1] \oplus G(v_i)\}$

最终 $G(u) = dp[u][m]$，其中 $m$ 是出边数量。

方法三：多游戏分析

对于 $k$ 个起始点 $r_1, r_2, \dots, r_k$，整体游戏的 SG 值为：

$$SG_{\text{total}} = G(r_1) \oplus G(r_2) \oplus \cdots \oplus G(r_k) $$

• 如果 $SG_{\text{total}} \neq 0$，先手（Alice）必胜
• 如果 $SG_{\text{total}} = 0$，后手（Bob）必胜

特殊情况分析

叶子节点

• 没有出边的节点：调用 dfs(u) 后立即返回，不暂停
• $G(\text{leaf}) = 0$（立即结束的游戏）

单一出边的情况

• 黑点：$G(u) = G(v)$
• 白点：$G(u) = \text{mex}\{0, G(v)\}$

多出边的顺序影响

由于出边是有序的，处理顺序影响最终结果：

• 黑点：顺序访问相当于序列游戏的 SG 值计算
• 白点：每个选择点提供分支

复杂度分析

• 预处理：拓扑排序 $O(n + m)$
• SG 值计算：每个节点处理其出边，总 $O(m)$
• 总复杂度：$O(n + m)$，满足数据范围要求

实现要点

1. 拓扑序处理：由于保证 $i < e_{i,j}$，可以直接从 $n$ 到 $1$ 逆序处理
2. SG 值计算：
   • 黑点：顺序异或所有子节点的 SG 值
   • 白点：维护当前值，对每条边计算 mex
3. 多游戏判断：计算所有起始点 SG 值的异或和

总结

本题的核心在于：

1. 博弈识别：认识到这是组合博弈问题
2. 建模转化：将 DFS 执行过程转化为 SG 函数计算
3. 分类处理：区分黑白节点的不同博弈行为
4. 多游戏分析：通过异或和判断整体胜负

这是一个典型的 组合博弈 + 图算法 难题，需要：

• 对组合博弈论的深刻理解
• 将实际问题形式化为数学模型的能力
• 处理 DAG 上动态规划的技巧

符合集训队互测题目的高难度标准。