题目理解

游戏规则

• 有一棵 n 个节点的树
• 初始时：一个红色节点（玩家1），一个蓝色节点（玩家2），其余白色
• 轮流行动：选择自己的一个有色节点，将其相邻的白色节点染成自己的颜色
• 无法行动者输

问题要求

给定集合 A（可能的红色初始位置）和 B（可能的蓝色初始位置），计算有多少对 (a, b) 使得玩家1有必胜策略。

关键观察

1. 游戏性质分析

这是一个** impartial game**（公平组合游戏），因为：

• 双方操作规则相同（染相邻白色节点）
• 节点一旦染色就不再改变
• 游戏区域是树，具有特殊的结构性质

2. 必胜条件分析

经过分析（原题背景知识），玩家1必胜当且仅当满足以下所有条件：

1. 红色节点的深度 ≤ 蓝色节点的深度
2. 红色节点 ≠ 蓝色节点
3. 如果深度相同，则颜色标记不同（即不在同一子树）

算法设计

1. 树的重心分解

// 寻找重心，平衡树结构
for (int i = 1; i <= n; ++i) {
    mxson[i] = std::max(mxson[i], n - sz[i]);
    if (mxson[i] * 2 <= n) {
        centroid.push_back(i);
    }
}

为什么用重心：

• 保证树深度最小化
• 便于后续的深度和颜色标记

2. 深度和颜色标记

if (centroid.size() == 1) {
    dfs2(centroid[0], 0, 1, 0);  // 单重心，所有节点颜色相同
} else {
    dfs2(centroid[0], centroid[1], 1, 0);  // 双重心，分别标记颜色
    dfs2(centroid[1], centroid[0], 1, 1);
}

• 深度：从重心开始的层数
• 颜色：在双重心情况下，标记节点属于哪个重心的子树

3. 三个计数任务

Task1: 深度条件计数

// 统计满足 dep_a <= dep_b 的节点对
void add(int is_A, int is_add, int d) {
    int delta = is_A ? query(0, n) - query(0, d - 1) : query(1, d);
    is_add ? ans += delta : ans -= delta;
    modify(is_A, d, is_add ? 1 : -1);
}

使用树状数组维护深度分布，高效计算满足深度条件的对数。

Task2: 排除相同节点

// 统计 A ∩ B，即排除 a = b 的情况
void add(int is_A, int is_add, int id) {
    int delta = exists[is_A ^ 1][id];
    is_add ? ans += delta : ans -= delta;
    exists[is_A][id] += is_add ? 1 : -1;
}

Task3: 同深度不同颜色

// 统计同深度但颜色不同的节点对
void add(int is_A, int is_add, int d, int c) {
    int delta = counts[is_A ^ 1][c ^ 1][d];
    is_add ? ans += delta : ans -= delta;
    counts[is_A][c][d] += is_add ? 1 : -1;
}

4. 最终答案计算

printf("%ld\n", t1.ans - t2.ans - t3.ans);

根据容斥原理：

最终答案 = (满足深度条件的对数) - (相同节点的对数) - (同深度同颜色的对数)

复杂度分析

• 预处理：两次DFS，O(n)
• 每次更新：树状数组操作，O(log n)
• 总复杂度：O(n + q log n)，可处理 n, q ≤ 5×10⁵

学习要点

1. 组合游戏建模

• 将游戏胜负条件转化为数学条件
• 利用树的性质简化分析

2. 重心分解技巧

• 平衡树结构，优化后续处理
• 双重心情况的特殊处理

3. 多条件计数

• 使用多个数据结构分别维护不同条件
• 容斥原理组合最终结果

4. 动态维护优化

• 树状数组支持高效更新和查询
• 实时响应集合变化

实例验证

以样例为例：

初始: A={1}, B={5,6}
计算过程：
t1.ans = 2 (所有满足深度条件的对)
t2.ans = 0 (没有相同节点)  
t3.ans = 1 (同深度同颜色的对)
最终: 2 - 0 - 1 = 1

这个解法巧妙地将复杂的游戏分析转化为清晰的计数问题，通过精心设计的数据结构高效处理大规模数据。