E. 黑白树 详细题解

问题重述

给定一棵 $n$ 个节点的树，每个节点是黑色（$c_i = 1$）或白色（$c_i = 0$），至少有 $2$ 个黑点。棋子在某个节点上，每次操作可以选择一个黑色顶点 $y$，然后将棋子沿着从当前位置到 $y$ 的最短路径的第一条边移动。连续两次操作不能选择同一个黑色顶点。当棋子移动到黑色顶点时结束。对于每个起始节点，判断是否存在操作序列使得棋子最终能到达黑色顶点。

关键观察

观察 1：操作的本质

从节点 $x$ 移动到相邻节点 $y$ 是可行的，如果存在一个黑色顶点使得路径经过 $y$ 且满足条件。实际上，我们可以将问题转化为：在什么情况下可以从 $x$ 沿着边 $x \to y$ 移动？

观察 2：可行移动的条件

考虑从 $x$ 沿着边 $x \to y$ 移动。设删除边 $(x, y)$ 后，$y$ 所在的连通分量为 $T_y$，$x$ 所在的连通分量为 $T_x$。从 $x$ 到 $y$ 的移动是可行的，如果满足以下任一条件：

1. $y$ 是黑色节点：移动后直接到达黑点，游戏结束，不需要下一次操作
2. $T_y$ 中至少有 $2$ 个黑点：可以用其中一个黑点作为本次移动的目标，另一个作为下次移动的目标（避免连续使用同一黑点）

注意：条件只依赖于 $y$ 侧的黑点数量，因为本次移动选择的黑点必须在 $T_y$ 中（否则路径不会先经过 $y$）。

观察 3：有向图的构建

根据上述条件，我们可以为每条无向边 $x-y$ 构建有向边：

• $x \to y$ 可行当且仅当：$c_y = 1$ 或 $T_y$ 中的黑点数 $\ge 2$
• $y \to x$ 可行当且仅当：$c_x = 1$ 或 $T_x$ 中的黑点数 $\ge 2$

观察 4：可达性分析

如果存在从节点 $i$ 到某个黑色节点的有向路径，则 $i$ 的答案为 $1$。为了方便计算，我们构建反向图（将每条有向边反向），然后从所有黑色节点出发进行 BFS/DFS，能到达的节点即为答案。

算法步骤

1. DFS 预处理：

   • 任选根节点（如 $0$），计算每个子树中的黑点数量 $cnt[u]$
   • 记录父节点 $par[u]$

2. 构建有向图：

   • 对于每条边 $u-v$：
     • 如果 $v$ 是 $u$ 的子节点（$par[v] = u$），则 $u \to v$ 可行当且仅当 $c_v = 1$ 或 $cnt[v] > 1$
     • 如果 $v$ 是 $u$ 的父节点，则 $u \to v$ 可行当且仅当 $c_v = 1$ 或 $cnt[0] - cnt[u] > 1$（$v$ 侧的黑点数 = 总黑点数减去 $u$ 子树中的黑点数）

3. 反向 BFS：

   • 将所有黑色节点加入队列
   • 在反向图上 BFS，标记所有可达节点

4. 输出结果：

   • 输出每个节点是否被标记

时间复杂度

• DFS 预处理：$O(n)$
• 构建有向图：$O(n)$
• BFS：$O(n)$
• 总复杂度：$O(n)$

完整代码

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

const int N = 300043;

vector<int> g[N];   // 原树
vector<int> g2[N];  // 反向有向图
int cnt[N];         // 子树中的黑点数量
int c[N];           // 节点颜色 (1=黑, 0=白)
int par[N];         // 父节点
int used[N];        // 是否可达

// DFS 计算子树黑点数量
void dfs(int x, int p = -1) {
    par[x] = p;
    cnt[x] = c[x];  // 先加上自己
    for (auto y : g[x]) {
        if (y != p) {
            dfs(y, x);
            cnt[x] += cnt[y];  // 累加子树的黑点
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    
    // 以 0 为根进行 DFS
    dfs(0);
    
    // 构建反向有向图
    for (int i = 0; i < n; i++) {
        for (auto j : g[i]) {
            // 判断 i -> j 是否可行
            bool can_move = false;
            
            if (i == par[j]) {
                // j 是 i 的子节点
                // i 侧的黑点数 = 总数 - cnt[j]
                int black_in_i_side = cnt[0] - cnt[j];
                if (c[j] == 1 || black_in_i_side > 1) {
                    can_move = true;
                }
            } else {
                // j 是 i 的父节点
                // i 侧的黑点数 = cnt[i]
                if (c[j] == 1 || cnt[i] > 1) {
                    can_move = true;
                }
            }
            
            if (can_move) {
                // 反向图：从 j 可以走到 i
                g2[j].push_back(i);
            }
        }
    }
    
    // 多源 BFS（从所有黑色节点出发）
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (c[i] == 1) {
            q.push(i);
            used[i] = 1;
        }
    }
    
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto to : g2[v]) {
            if (!used[to]) {
                used[to] = 1;
                q.push(to);
            }
        }
    }
    
    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << used[i] << " \n"[i == n - 1];
    }
    
    return 0;
}

代码说明

1. DFS 预处理：

   • cnt[x] 表示以 $x$ 为根的子树中的黑点数量
   • par[x] 记录父节点，用于判断边的方向

2. 可行移动判断：

   • 对于边 $i-j$，需要根据方向分别判断
   • 子节点方向：检查父节点侧的黑点数（总数减去子节点子树）
   • 父节点方向：检查子节点侧的黑点数（即子节点子树）

3. 反向图 BFS：

   • 从所有黑点出发，沿着反向边遍历
   • 标记所有能到达的节点

4. 输出：

   • used[i] = 1 表示可以从节点 $i$ 到达黑点

示例验证

以题目样例为例：

8
0 1 0 0 0 0 1 0
边：(8,6), (2,5), (7,8), (6,5), (4,5), (6,1), (7,3)

• 黑点：节点 2（索引 1）和节点 7（索引 6）
• 输出：0 1 1 1 1 0 1 1
• 节点 1（索引 0）无法到达黑点，输出 0
• 节点 6（索引 5）无法到达黑点，输出 0
• 其他节点都可以到达黑点

总结

本题的核心技巧：

1. 将移动可行性转化为子树黑点数的条件
2. 构建有向图表示可行移动
3. 使用反向图 + BFS 计算可达性
4. 利用树的性质在 $O(n)$ 时间内完成所有计算