题目大意

给定一棵 $n$ 个节点的博弈树，根节点为黑方决策，黑白方交替决策。
叶节点状态未知，但可以定义：

• 黑方胜集合：若集合中所有叶节点为黑方胜，则根节点黑方胜
• 最小黑方胜集合：元素个数最少的黑方胜集合
• 最小白方胜集合：类似定义
• 关键叶节点：同时属于某个最小黑方胜集合和某个最小白方胜集合的叶节点

要求找出所有关键叶节点，并输出：

1. 最小编号
2. 总个数
3. 所有编号的异或和

---

问题分析

1. 博弈规则

• 黑方决策节点：只要有一个儿子是黑方胜，该节点就是黑方胜
• 白方决策节点：只要有一个儿子是白方胜，该节点就是白方胜
• 叶节点状态未知，但我们需要知道最少需要确定哪些叶节点状态，就能确定根节点胜负

---

核心思路：树形DP

1. 状态定义

设：

• $f[u]$：以 $u$ 为根的子树，要使 $u$ 为黑方胜，需要确定的最少叶节点数量
• $g[u]$：以 $u$ 为根的子树，要使 $u$ 为白方胜，需要确定的最少叶节点数量

---

2. 状态转移

情况 1：$u$ 是叶节点

• 要使 $u$ 黑方胜：必须确定 $u$ 为黑方胜 ⇒ $f[u] = 1$
• 要使 $u$ 白方胜：必须确定 $u$ 为白方胜 ⇒ $g[u] = 1$

情况 2：$u$ 是黑方决策节点

• 要使 $u$ 黑方胜：至少一个儿子黑方胜 ⇒ $f[u] = \min\limits_{v \in son(u)} f[v]$
• 要使 $u$ 白方胜：所有儿子都必须白方胜 ⇒ $g[u] = \sum\limits_{v \in son(u)} g[v]$

情况 3：$u$ 是白方决策节点

• 要使 $u$ 黑方胜：所有儿子都必须黑方胜 ⇒ $f[u] = \sum\limits_{v \in son(u)} f[v]$
• 要使 $u$ 白方胜：至少一个儿子白方胜 ⇒ $g[u] = \min\limits_{v \in son(u)} g[v]$

---

3. 关键叶节点的判定

设根节点 $1$ 的：

• 最小黑方胜集合大小 = $F = f[1]$
• 最小白方胜集合大小 = $G = g[1]$

对每个叶节点 $u$，判断它是否同时出现在某个最小黑方胜集合和某个最小白方胜集合中。

---

判定方法

我们从根向下传递信息，判断每个叶节点是否能成为最小方案的一部分：

定义：

• $canF[u]$：$u$ 是否可能出现在以 $u$ 子树根的最小黑方胜集合中
• $canG[u]$：$u$ 是否可能出现在以 $u$ 子树根的最小白方胜集合中

初始：$canF[1] = canG[1] = true$

向下传递规则：

• 如果 $u$ 是黑方节点：

  • 要使 $u$ 黑方胜且 $u$ 在最小黑方胜集合中，必须选择那个 $f[v]$ 最小的儿子（可能有多个）
  • 所以对满足 $f[v] = f[u]$ 的儿子 $v$，$canF[v] = canF[u]$
  • 要使 $u$ 白方胜且 $u$ 在最小白方胜集合中，需要所有儿子都在对应白方胜集合中
  • 所以对所有儿子 $v$，$canG[v] = canG[u]$

• 如果 $u$ 是白方节点：

  • 要使 $u$ 黑方胜且 $u$ 在最小黑方胜集合中，需要所有儿子都在对应黑方胜集合中
  • 所以对所有儿子 $v$，$canF[v] = canF[u]$
  • 要使 $u$ 白方胜且 $u$ 在最小白方胜集合中，必须选择那个 $g[v]$ 最小的儿子
  • 所以对满足 $g[v] = g[u]$ 的儿子 $v$，$canG[v] = canG[u]$

---

4. 最终判断

对于叶节点 $u$：

• 如果 $canF[u] = true$ 且 $canG[u] = true$，则 $u$ 是关键叶节点

---

算法步骤

1. 建树：根据输入建立树结构，标记每个节点的决策方（根为黑方，交替）
2. 第一次DFS：计算 $f[u]$ 和 $g[u]$
3. 第二次DFS：传递 $canF[u]$ 和 $canG[u]$
4. 统计：遍历所有叶节点，收集关键叶节点信息

---

复杂度分析

• 两次DFS：$O(n)$
• 满足 $n \leq 2\times 10^5$ 的要求

---

样例验证

样例树：

      1(黑)
     /     \
   2(白)   3(白)
  /   \    /   \
4(黑) 5(黑) 6(黑) 7(黑)

计算：

• 叶节点：$f=g=1$
• 节点2（白）：$f=1+1=2$, $g=\min(1,1)=1$
• 节点3（白）：$f=1+1=2$, $g=\min(1,1)=1$
• 根节点1（黑）：$f=\min(2,2)=2$, $g=1+1=2$

最小黑方胜集合大小 = 2，最小白方胜集合大小 = 2

通过传递标记发现所有叶节点都同时出现在某个最小黑方胜集合和某个最小白方胜集合中，因此关键叶节点为 {4,5,6,7}。

---

总结

这道题通过两次树形DP：

1. 自底向上计算最小获胜集合大小
2. 自顶向下标记可能出现在最小集合中的叶节点

从而高效找出所有关键叶节点，结合了博弈树性质和树形DP的技巧。