题意整理

• 有一棵 $n$ 个节点的树，每个节点 $i$ 上有 $a_i$ 个棋子。
• 游戏规则：每次可将节点 $u$ 的一个棋子移到它的子树内（不含 $u$ 本身）的任意节点。不能动者输。
• 特殊能力：
  • C：在游戏开始前，可以把根 $R$ 换成一个相邻节点 $R'$。
  • K：在游戏开始前，可以在任意一个节点加一个棋子。
• 每局游戏流程：
  1. 初始在节点 $x$ 放一个棋子，根设为 $y$。
  2. C 决定是否发动能力（换根到相邻节点，或不发动）。
  3. K 决定是否发动能力（在任意节点加一个棋子）。
  4. 进行正常游戏（C 先手）。
  5. 还原到步骤 1 结束的状态（即 $x$ 上多一个棋子，其他 $a_i$ 不变）。
• 问：C 在步骤 2 有多少种决策（换到哪个相邻根，或不换），使得 无论 K 在步骤 3 如何操作，C 都必胜。

关键分析

1. 基础博弈模型

这是一个多堆石子的变形，但移动限制在子树内（不含自己）。

实际上，这是一个有向图游戏：每个节点是一个子游戏，棋子在不同节点独立。
根据 SG 定理，整局游戏的 SG 值是每个有棋子节点的 SG 值的异或和。

定义 $sg(u)$ 表示以 $u$ 为根的子树的 SG 值（考虑 $u$ 上的棋子可以走到子树内其他节点）。

关键结论（经典树上 Green Hackenbush / 子树移动博弈）：

• 叶子节点：$sg(u) = 0$（因为不能移动）。
• 对于非叶子节点 $u$，若其儿子节点为 $v_1, v_2, \dots, v_k$，则： [ sg(u) = \bigoplus_{i=1}^k (sg(v_i) + 1) ] 原因：从 $u$ 可以走到每个 $v_i$ 子树，相当于每个子游戏 $sg(v_i)$ 加上一步操作（即 $sg(v_i) + 1$），然后组合游戏的 SG 值是它们的异或和。

2. 初始局面

初始时，我们在 $x$ 上额外放一个棋子（步骤 1），所以初始局面的 SG 值 = $sg_{\text{root}}(x)$（这里 $sg_{\text{root}}(t)$ 表示在给定根下节点 $t$ 的 SG 值）。

但注意，根的位置会影响 $sg$ 的计算，因为 $sg(u)$ 依赖于以 $u$ 为根的子树结构。

3. 特殊能力的影响

• K 的能力：可以在任意节点加一个棋子。这相当于在 SG 值中异或上该节点的 SG 值。K 的目标是让总 SG 值 = 0（使 C 必败）。
• C 的能力：换根到相邻节点。这会改变整棵树的 SG 值计算，因为根变了，所有节点的 $sg$ 值都会变。

4. 问题转化

C 要必胜，必须保证：无论 K 在哪个节点加一个棋子，最终 SG 值 ≠ 0。

设初始根为 $y$，在 $x$ 上多一个棋子，初始 SG = $sg_y(x)$。

若 C 不换根，K 可以选择在节点 $t$ 加棋子，使： [ sg_y(x) \oplus sg_y(t) = 0 ] 即 $sg_y(t) = sg_y(x)$。只要存在一个 $t$ 使得这个等式成立，K 就能让 C 输。

所以 C 不换根能必胜的条件是：不存在任何节点 $t$ 使得 $sg_y(t) = sg_y(x)$。

若 C 换根到 $y'$（与 $y$ 相邻），则初始 SG 值变为 $sg_{y'}(x)$。
C 必胜的条件是：对于所有节点 $t$，$sg_{y'}(t) \neq sg_{y'}(x)$。

算法步骤

1. 预处理所有根情况下的 $sg$ 值
   用换根 DP：

   • 第一次 DFS 计算 $sg_1(u)$（以 1 为根）。
   • 第二次 DFS 换根：当根从 $u$ 移到 $v$（$v$ 是 $u$ 的儿子）时：
     • 原 $sg_u(v)$ 已知。
     • 新根 $v$ 的 $sg_v(u)$ 需要计算：把 $u$ 视为 $v$ 的儿子，其他儿子不变，用 SG 公式： [ sg_v(u) = \left( sg_u(u) \oplus (sg_u(v)+1) \right) + 1 ] 这里 $sg_u(u)$ 是原根 $u$ 的 SG 值，去掉 $v$ 子树的影响（即异或掉 $sg_u(v)+1$），然后加上 $u$ 作为 $v$ 的儿子时多的一步（+1）。

2. 对每个根 $r$，统计 $sg_r(\cdot)$ 的频率
   用哈希表记录每个 $sg$ 值出现的次数。

3. 回答询问
   对于 $(x, y)$：

   • 检查根 $y$ 时，$sg_y(x)$ 出现次数是否为 1（即只有 $x$ 本身是这个值）。如果是，则 C 不换根就必胜（1 种方案）。
   • 对 $y$ 的每个邻居 $y'$，检查根 $y'$ 时，$sg_{y'}(x)$ 出现次数是否为 1。每个满足的邻居算 1 种方案。
   • 总方案数 = 不换根（若可行）+ 换根到满足条件的邻居数。

时间复杂度

• 两次 DFS：$O(n)$
• 每次询问检查邻居：$O(\text{deg}(y))$
• 总复杂度：$O(n + m \cdot \text{max degree})$，可过。