题目概述

给定一棵 $n$ 个节点的树，每个节点要么是已存在的基站（标记为 '0'），要么是需要被覆盖的普通节点（标记为 '1'）。有 $Q$ 个查询，每个查询给定一个覆盖半径 $X$，要求：

1. 确保所有普通节点（'1'）都被覆盖（包括已存在基站的覆盖或新增基站的覆盖）；
2. 新增基站的数量最少；
3. 若存在普通节点无法被覆盖（即使新增基站也不行），输出 -1。

核心思路

1. 预处理：初始覆盖判断

首先通过 BFS 计算每个节点到最近已存在基站（'0'）的距离 $dis[]$。对于每个查询 $X$：

• 若存在普通节点（'1'）的 $dis[] > X$，说明该节点无法被原有基站覆盖，必须通过新增基站覆盖；
• 若新增基站后仍无法覆盖（实际通过后续 BFS 验证），输出 -1。

2. 反向 BFS：确定必须覆盖的节点

对于查询 $X$，构造“必须覆盖的节点集合”——所有 $dis[] > X$ 的节点（包括普通节点和可能的基站节点）。通过 BFS 计算这些节点到最近“必须覆盖节点”的距离 $dis2[]$：

• 若存在普通节点的 $dis2[] > X$，说明即使在所有必须覆盖的节点上建基站，该普通节点仍无法被覆盖，输出 -1。

3. 贪心 DFS：最少新增基站

采用树形贪心策略，从叶子向根遍历：

• 记录每个节点的覆盖状态 $f[u]$，包含状态标记和有效覆盖距离；
• 当节点的子树中存在未被覆盖的节点，且当前节点到最近新增基站的距离超过 $X$ 时，在当前节点新增基站，更新覆盖状态。

算法步骤

步骤 1：初始 BFS 计算初始覆盖距离

• 收集所有已存在的基站（'0' 节点）作为初始源点，BFS 计算每个节点到最近基站的距离 $dis[]$，存入 $dis$ 数组。

步骤 2：处理每个查询

1. 筛选必须覆盖的节点：收集所有 $dis[u] > X$ 的节点，记为 $pt$；
2. 反向 BFS 计算 $dis2[]$：以 $pt$ 为源点 BFS，计算每个节点到最近“必须覆盖节点”的距离 $dis2[]$；
3. 可行性判断：若存在普通节点（'1'）的 $dis2[u] > X$，输出 -1；
4. 贪心 DFS 计算最少新增基站：从根节点（1 号节点）开始，深度优先遍历树，维护每个节点的覆盖状态，贪心新增基站。

步骤 3：贪心 DFS 细节

• 状态定义：$f[u] = (type, val)$，其中：
  • $type = -1$：子树中存在未被覆盖的节点；
  • $type = 0$：子树已被完全覆盖；
  • $type = 1$：当前节点是新增基站，$val$ 为该基站的覆盖半径剩余距离；
• 状态合并：通过 $chk()$ 函数合并子节点的状态，优先保留未覆盖状态和有效覆盖距离；
• 基站新增条件：当节点 $u$ 的子树存在未被覆盖的节点，且父节点的覆盖无法延伸到当前节点时，在 $u$ 新增基站，更新 $f[u]$ 为新增基站状态。

关键函数解析

1. 初始 BFS 函数

void bfs(vector<int> S, int dis[]) {
    queue<int> q;
    for (int i = 1; i <= n; i++) dis[i] = INF;
    for (int u : S) dis[u] = 0, q.push(u);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : G[u])
            if (dis[v] == INF)
                dis[v] = dis[u] + 1, q.push(v);
    }
}

• 功能：计算多个源点到所有节点的最短距离（树中无环，最短距离唯一）；
• 应用场景：初始覆盖距离计算（源点为已存在基站）和反向覆盖距离计算（源点为必须覆盖节点）。

2. 状态合并函数 $chk()$

pii chk(pii x, pii y) {
    if (x.FR == 0) return y;
    if (y.FR == 0) return x;
    if (x.FR == -1) swap(x, y);
    if (x.FR == -1) return {x.FR, max(x.SE, y.SE)};
    if (y.FR == -1) return (x.SE + y.SE <= X ? x : y);
    return {x.FR, min(x.SE, y.SE)};
}

• 功能：合并两个子节点的覆盖状态，优先处理未覆盖状态，确保覆盖范围最大化；
• 逻辑：
  • 若一个状态为已覆盖（$type=0$），直接返回另一个状态；
  • 若存在未覆盖状态（$type=-1$），保留该状态并记录最大需要覆盖的距离；
  • 若存在新增基站状态（$type=1$），判断是否能覆盖未覆盖节点，否则保留未覆盖状态。

3. 贪心 DFS 函数

void dfs(int u, int fa) {
    f[u] = {s[u] == '1' ? -1 : 0, 0}; // 初始状态：普通节点未覆盖，基站已覆盖
    for (int v : G[u]) {
        if (v == fa) continue;
        dfs(v, u);
        if (f[v].FR) f[v].SE++; // 子节点状态向上传递，距离+1
        f[u] = chk(f[u], f[v]); // 合并子节点状态
    }
    // 若子树存在未覆盖节点，且父节点无法覆盖，新增基站
    if (!~f[u].FR) {
        if (!fa || dis2[fa] + 1 + f[u].SE > X) {
            ans++;
            f[u] = {1, dis2[u]}; // 标记为新增基站，记录覆盖半径
        }
    }
}

• 功能：从叶子向根遍历，贪心新增基站，确保覆盖所有未被覆盖的节点；
• 核心逻辑：
  • 初始状态：普通节点默认未覆盖，基站默认已覆盖；
  • 合并子节点状态后，若当前节点子树存在未覆盖节点，且父节点的覆盖无法延伸到当前节点（距离超过 $X$），则新增基站；
  • 新增基站后，更新节点状态为基站，其覆盖半径为 $dis2[u]$（到最近必须覆盖节点的距离）。

时间复杂度分析

• 初始 BFS：$O(n)$，仅执行一次；
• 每个查询：
  • 反向 BFS：$O(n)$；
  • 贪心 DFS：$O(n)$；
• 总时间复杂度：$O(n + Q \cdot n)$，适用于 $n \leq 1e5$、$Q \leq 1e5$ 的场景（实际需注意常数优化）。

边界情况处理

1. 已存在的基站足够覆盖所有普通节点（$dis[u] \leq X$ 对所有 '1' 节点成立）：此时无需新增基站，输出 0；
2. 普通节点无法被覆盖（$dis2[u] > X$）：输出 -1；
3. 树为链状结构：贪心策略仍有效，从叶子向根新增基站，确保覆盖范围最大化。

总结

本题的核心是树形贪心与多源 BFS 的结合：

• 多源 BFS 用于快速计算节点间的最短距离，判断覆盖可行性；
• 树形贪心通过自底向上的状态合并，确保新增基站数量最少。

该算法高效处理了树上的覆盖问题，充分利用了树的无环特性和贪心策略的最优性，适用于大规模输入场景。