A. Iris 与树上的游戏 详细题解

问题重述

有一棵以 $1$ 为根的树，每个节点值为 $0$ 或 $1$（部分未知，用 ? 表示）。定义叶子的权值为从根到该叶子的路径字符串中 10 子串出现次数减去 01 子串出现次数。树的得分为权值非零的叶子数量。Iris 先手，两人轮流将 ? 改为 $0$ 或 $1$，Iris 想最大化最终得分，Dora 想最小化。求最终得分。

关键观察

观察 1：权值的简化

考虑路径字符串，删除所有连续相同字符的重复部分（只保留变化点），得到一个新字符串，其中相邻字符都不同。例如：$110001 \rightarrow 101$。

在这个简化字符串中：

• 每对相邻的 $01$ 或 $10$ 对应原字符串中的一次变化
• 简化字符串的长度为 $m$，则原字符串中 $01$ 和 $10$ 的总数为 $m-1$

更关键的是：叶子的权值非零当且仅当根的值与叶子的值不同。

证明：

• 如果根与叶子值相同，简化字符串长度为奇数，$01$ 和 $10$ 数量相等，差为 $0$
• 如果根与叶子值不同，简化字符串长度为偶数，$01$ 和 $10$ 数量相差 $1$，差为 $\pm 1$

因此，问题转化为：统计有多少叶子，其值最终与根的值不同。

观察 2：已知根值的情况

如果根的值已经确定（$0$ 或 $1$），那么：

• Iris 希望叶子值与根值不同（这样权值非零）
• Dora 希望叶子值与根值相同（这样权值为零）

设：

• $x$ = 已确定为与根值相同的叶子数量
• $y$ = 已确定为与根值不同的叶子数量
• $z$ = 值为 ? 的叶子数量

对于 ? 叶子，谁有机会决定它的值？

• 如果 $z$ 是奇数，Iris 可以多决定一个叶子（因为她先手）
• 最终与根值不同的叶子数 = $y + \lceil z/2 \rceil$（Iris 会尽量让 ? 叶子变成与根不同）

观察 3：根值未知的情况

当根的值也未知时，情况更复杂。Iris 可以在第一步决定根的值，但需要考虑叶子中 $0$ 和 $1$ 的分布。

设：

• $x$ = 已确定为 $0$ 的叶子数量
• $y$ = 已确定为 $1$ 的叶子数量
• $z$ = 值为 ? 的叶子数量
• $w$ = 既不是根也不是叶子的 ? 节点数量（内部 ? 节点）

关键结论：

• 如果 $x \ne y$，Iris 可以先将根设为与较多叶子相同的值，然后按照已知根的情况处理
• 如果 $x = y$，双方会先处理内部 ? 节点，因为先处理根会失去优势

观察 4：内部 ? 节点的影响

当 $x = y$ 且 $w$ 为奇数时：

• Dora 将不得不处理最后一个内部节点，然后轮到 Iris 处理根
• Iris 可以设置根的值，使与根不同的叶子数多 $1$

因此，最终公式为：

• 当 $x \ne y$ 时：$\max(x, y) + \lceil z/2 \rceil$
• 当 $x = y$ 时：$x + \lceil (z + (w \bmod 2)) / 2 \rceil$

算法步骤

1. 读入 $n$，构建树的邻接表，记录每个节点的度数
2. 读入字符串 $s$（$1$-based）
3. 统计：
   • $x$：叶子中值为 $0$ 的数量
   • $y$：叶子中值为 $1$ 的数量
   • $z$：叶子中值为 ? 的数量
   • $w$：非根非叶子节点中值为 ? 的数量
4. 根据 $s[1]$ 的值计算答案：
   • 若 $s[1] = 0$：输出 $y + \lceil z/2 \rceil$
   • 若 $s[1] = 1$：输出 $x + \lceil z/2 \rceil$
   • 若 $s[1] = ?$：输出 $\max(x, y) + \lceil (z + (w \bmod 2 \text{ if } x = y \text{ else } 0)) / 2 \rceil$

时间复杂度

• 每个测试用例 $O(n)$
• 总复杂度 $O(\sum n) \le 2 \times 10^5$

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        vector<int> deg(n + 1, 0);
        
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            deg[u]++;
            deg[v]++;
        }
        
        string s;
        cin >> s;
        s = " " + s;  // 1-based indexing
        
        int x = 0, y = 0, z = 0, w = 0;  // x=0叶子, y=1叶子, z=?叶子, w=内部?节点
        
        for (int i = 2; i <= n; i++) {  // 从2开始，跳过根节点
            if (deg[i] == 1) {  // 叶子节点
                if (s[i] == '0') x++;
                else if (s[i] == '1') y++;
                else z++;
            } else {  // 内部节点（非根非叶子）
                if (s[i] == '?') w++;
            }
        }
        
        int ans;
        
        if (s[1] == '0') {
            ans = y + (z + 1) / 2;
        } else if (s[1] == '1') {
            ans = x + (z + 1) / 2;
        } else {  // s[1] == '?'
            if (x == y) {
                ans = x + (z + (w % 2)) / 2;
            } else {
                ans = max(x, y) + (z + 1) / 2;
            }
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}

代码说明

1. 度数统计：deg[i] 记录节点 $i$ 的度数，度数为 $1$ 且不是根的是叶子
2. 分类统计：
   • $x$：确定值为 $0$ 的叶子
   • $y$：确定值为 $1$ 的叶子
   • $z$：值为 ? 的叶子
   • $w$：内部（非根非叶子）值为 ? 的节点
3. 答案计算：
   • 根确定时：Iris 可以控制 $\lceil z/2 \rceil$ 个 ? 叶子变为对自己有利的值
   • 根不确定且 $x \ne y$：Iris 将根设为多数叶子的值，然后按根确定情况处理
   • 根不确定且 $x = y$：双方先处理内部 ?，最后处理根，$w$ 的奇偶性影响结果

示例验证

以第一个测试用例为例：

• $n=4$，叶子为 $2,3,4$
• $s = 0101$，根 $s[1]=0$
• $x=1$（叶子3值为0），$y=2$（叶子2和4值为1），$z=0$
• 答案 = $y + \lceil 0/2 \rceil = 2$，与输出一致

总结

本题的核心技巧：

1. 将叶子权值非零的条件简化为：叶子值与根值不同
2. 根据根是否已知分类讨论
3. 利用博弈的先后手优势计算 ? 叶子的分配
4. 当 $x=y$ 时，内部 ? 节点的奇偶性影响最终结果