一、题意理解

游戏规则

• 有一个 $n$ 个点（车站）、$m$ 条有向边（单向轨道）的有向图，每个点至少一条出边。
• 每个点有拥有者：$a_i=1$ 表示 Arezou 控制，$a_i=0$ 表示 Borzou 控制。
• 每个点有充电属性：$r_i=1$ 表示是充电站。
• 火车初始位置在 $s$，初始电量满电。
• 满电可以连续走 $n$ 条边，走第 $n+1$ 条边之前没充电就会停电（Borzou 赢）。
• 开关规则：
  • 第一次到达一个车站时，该车站的拥有者决定火车从该车站选择哪条出边，之后这个选择锁定（再到达时走同一条边）。
  • 游戏开始时，初始车站 $s$ 的拥有者先选择第一条边。
• 火车不断走，因为出边锁定，最终会进入一个环路。
• Arezou 胜利条件：环路中存在充电站（火车能不断充电无限行驶）。
  Borzou 胜利条件：环路中没有充电站（电量耗尽停车）。

---

问题转化

我们需要对每个起点 $s$ 判断：Arezou 是否有必胜策略（即无论 Borzou 在控制的车站如何选择出边，Arezou 都能迫使火车进入一个含充电站的环路）。

这是不完全信息博弈吗？不是，是完全信息的：双方都知道所有车站的归属与充电属性。

这是一个确定性的无限回合游戏，因为选择一旦锁定就固定，游戏最终进入环。

---

二、状态与博弈分析

1. 状态定义

游戏的一个状态 = (当前车站 $v$, 剩余电量 $e$)，其中 $0 \le e \le n$（满电为 $n$，走一条边减 1，到充电站恢复为 $n$）。

状态总数 $O(n^2) \le 25\times 10^6$，可接受 DP/搜索。

---

2. 玩家回合

在状态 $(v, e)$：

• 如果 $e=0$（已没电），Borzou 已经赢（游戏结束），但根据规则，没电发生在“即将进入下一条边之前”，因此游戏在进入 $(v,0)$ 时 Borzou 已胜，不会继续移动。
• 否则，轮到车站 $v$ 的拥有者选择一条 $v$ 的出边 $v\to t$，然后火车移动到 $t$，电量变化：
  • 如果 $r_t = 1$：电量恢复为 $n$。
  • 否则：电量 $e' = e - 1$（若 $e' = 0$，则火车在到达 $t$ 后即将移动前没电）。

但要注意：游戏胜利判据是最终进入的环中是否有充电站，而不是中间电量是否耗光。
也就是说，如果进入了一个无充电站的环，即使当前还有电，也会在若干圈后耗尽（Borzou 赢）。
如果进入有充电站的环，则永远不耗尽（Arezou 赢）。

因此我们需要分析环路而不是单纯看电量状态。

---

三、关键观察

1. 锁定效应与环路

一旦所有点都被访问过（出边锁定），之后的路径就是固定的循环。

设火车依次访问的车站序列为 $p_0, p_1, p_2, \dots$（$p_0=s$），每个 $p_i$ 的出边选择是在第一次到达 $p_i$ 时决定的。

所以游戏的策略其实是为每个车站预先选好一条出边，但选择顺序是按第一次到达顺序。

---

2. 等价于“选择出边”博弈

我们可以换一个角度：游戏开始时，每个车站的出边未定。
玩家在火车第一次到达某个车站时，为该车站选择一条出边（且以后不变）。

那么 Arezou 的目标是：存在一种策略（对 Arezou 控制的车站选边），使得无论 Borzou 如何选边（对他控制的车站），最终环路包含充电站。

---

三、化为图上的必胜点判定

1. 经典方法：反向 BFS（类似拓扑）

定义赢状态为“从该状态出发，Arezou 有必胜策略”。

考虑最终局面：火车在一个环路 $C$ 上。

• 如果 $C$ 中有充电站 → Arezou 赢。
• 如果 $C$ 中没有充电站 → Borzou 赢。

因此，Arezou 的策略是迫使进入含充电站的环，Borzou 的策略是迫使进入无充电站的环。

---

2. 化为“安全点”概念

定义好环：含有至少一个充电站的环路。
定义坏环：没有充电站的环路。

游戏可看作：火车在图上走，每次到达新车站时由该站拥有者选择一条出边。
Arezou 的目标是让火车无限走下去（即进入好环），Borzou 的目标是让火车进入坏环（最终停电）。

---

3. 必胜/必败分析框架

这是一个两人零和博弈，可以建模为有向图上的博弈（Generalized geography 类），但更复杂，因为状态包括“哪些点已锁定”。

我们可以简化：不考虑电量，只考虑最终进入的环的性质。为什么？

• 电量只是限制了环的长度必须能使火车在耗尽前遇到充电站吗？不对，环固定后，如果环中无充电站，则无论多少电都会在若干圈后耗尽。
• 所以关键是：Arezou 要保证进入的环含有充电站。

因此问题化为：是否存在 Arezou 的选择策略，使得无论 Borzou 怎么选，火车最终进入的环一定含充电站。

---

四、官方题解核心思路

实际上，IOI 2017 官方解法利用了交替推进的归纳过程。

步骤：

1. 我们想找出所有 Arezou 必胜的起点 $s$。
2. 定义安全点：从该点出发，Arezou 能保证进入一个好环（含充电站）。
3. 初始：所有充电站本身是安全点吗？ 不一定，因为如果充电站被 Borzou 控制，他可以选择一条出边去坏环。
4. 用反向推理：
   • 如果一个点 $v$ 被 Arezou 控制，并且它有一条出边通向某个安全点 → 则 $v$ 也是安全点（因为 Arezou 可以选择那条边）。
   • 如果一个点 $v$ 被 Borzou 控制，并且所有出边都通向安全点 → 则 $v$ 也是安全点（因为 Borzou 无论如何选都会到安全点）。
   • 重复这个过程直到不动点，标记出所有安全点。
5. 对于非安全点，Borzou 有策略迫使进入坏环。

但这里有个问题：安全点定义依赖于“进入好环”的可能性，但好环可能由多个点组成，且好环本身也需要安全点组成闭环。

---

更精确的方法（类似 Büchi 游戏）

将问题建模为 Büchi 游戏：

• 目标：无限次访问充电站（这样能无限充电）。
• 图状态就是车站（因为出边选择权归车站拥有者）。
• 这是两人有向图博弈，玩家 $A$（Arezou）控制 $a_i=1$ 的点，玩家 $B$（Borzou）控制 $a_i=0$ 的点。
• 胜利条件：无限路径中充电站出现无限多次。

Büchi 游戏可以用** Zielonka 算法**求解，复杂度 $O(m)$。

---

具体算法（简化描述）：

1. 先找出所有必然能到达充电站的点（不考虑玩家控制）？不够，因为对手会干扰。

2. 用交替不动点算法：

   • 设 $W_A$ 是 Arezou 必胜点的集合，初始为空。
   • 定义 $Attr_A(S)$：Arezou 能保证一步内进入 $S$ 的点集（对 Arezou 控制的点，只需一条出边到 $S$；对 Borzou 控制的点，需所有出边到 $S$）。
   • 从充电站出发，反复计算 $W_A$ 的吸引子，并逐步扩展 $W_A$。

   更标准的 Büchi 游戏解法（Zielonka）：

   • 递归计算最大不动点。
   • 步骤：
     1. 找到所有充电站，设为 $F$。
     2. 计算从 $F$ 出发 Arezou 能保证回到 $F$ 的区域（即 $F$ 的递归吸引子）。
     3. 递归处理剩下的子游戏。

   由于 $n\le 5000$，可用 $O(nm)$ 实现。

---

五、实现步骤概要

1. 建模

建图 $G$，记录每个点的出边列表。

2. 计算 Arezou 必胜点集 $W$

初始化 $W = \emptyset$。 重复直到收敛：

1. 在子图 $G$ 上，找所有充电站且属于当前 $W$ 或新加入的？ 更准确： 我们先找所有充电站 $r_i=1$ 的点，它们是 Arezou 的“目标”。 计算 $T = \{ v \mid v \text{ 是充电站} \}$。 计算 $Attr_A(T)$ 加入 $W$。 然后在剩余图上递归。

Zielonka 递归伪代码：

solve(G, F):
    if G 为空: return 空集
    计算 X = Attr_A(G, F)  # Arezou 能保证进入 F 的点集
    Y = solve(G \ X, F \ X)  # 在剩余图上递归
    计算 Z = Attr_A(G, Y)
    return X ∪ Z

初始 $F$ = 所有充电站集合，调用 solve(全体点, F) 得到 Arezou 必胜点。

3. 答案

对每个起点 $s$，若 $s \in W$ 则 $w[s]=1$，否则 $0$。

---

六、举例说明

简单图：3 个点 0,1,2。

• 充电站：0。
• 拥有者：0 归 Arezou，1 归 Arezou，2 归 Borzou。
• 边：0→1, 0→2；1→2；2→2。

分析：

• 点 2 是自环（无充电站），Borzou 控制。
• 从 0 开始：Arezou 选边。若选 0→1（Arezou 控制 1），1 可到 2（Borzou 控制 2），2 进入自环坏环 → Borzou 赢。 若选 0→2（直接到坏环）→ Borzou 赢。 所以 0 不是必胜点。
• 从 1 开始：Arezou 控制 1，只能到 2（坏环）→ 输。
• 从 2 开始：Borzou 控制，直接坏环输（不对，这里 Arezou 要赢需要保证赢，但 Borzou 控制 2 时肯定选坏环，所以 Arezou 不能赢）。

因此 $w = [0,0,0]$。

---

七、复杂度

• 每次计算 Attr_A 可 BFS 实现 $O(n+m)$。
• 递归深度 $O(n)$，总复杂度 $O(n(n+m))$，最坏 $25\times 10^6$ 左右，可过。

---

八、总结

这道题的本质是：

1. Büchi 游戏（无限路径需无限次访问充电站）。
2. 用 Zielonka 递归算法 求解两人有向图博弈。
3. 核心操作是交替吸引子计算（对 Arezou 控制的点：存在一条边进入目标；对 Borzou 控制的点：所有边进入目标）。

算法思维层次较高，是博弈论在图论中的经典应用。