【蓝桥杯】雪地工程核弹引爆控制器最小数量计算

问题描述

危机纪元 2211 年，由罗辑领导的雪地工程正式进入部署，雪地工程中布置了大量的核弹，整个工程由信号中转站和起爆装置构成，形成了一棵具有 nn 个点 n−1n−1 条边的有根树，11 号点为根节点，树边为 (ui,vi)(ui​,vi​) 。 起爆装置为度为 11 并且不是根的节点，其余节点为信号中转站，预先在 mm 个起爆装置上面布置有核弹，为了引爆核弹，会在 11 号节点施加一个引爆信号，在信号中转站上，该信号会随机向某一个子节点传输，为了避免核弹不被引爆，你可以在信号中转站上面安装控制器，使得引爆信号只会往指定的子节点传输，为了减少开销，你能帮帮罗辑计算最少需要安装的控制器数量吗？

输入格式

第 11 行包含一个正整数 nn（2≤ n ≤ 1052≤ n ≤ 105），表示树点的数量。 第 2∼n+12∼n+1 行每行包含 22 个正整数 ui,viui​,vi​（1≤ui,vi≤n1≤ui​,vi​≤n），分别表示树边的两个端点。 接下来 11 行包含一个正整数 mm (1≤ m ≤1≤ m ≤ 叶子数量) ，表示含有核弹的起爆装置的数量。 再接下来 11 行包含 mm 个整数 ， 表示具有核弹起爆装置的节点编号。

输出格式

输出一个数字，表示需要放置的最小控制器数量。

样例输入

5 1 2 1 3 1 4 2 5 2 4 5

样例输出

#include using namespace std; int main() { int n; cin » n; vector> adj(n + 1); // 邻接表 for (int i = 0; i < n - 1; ++i) { int u, v; cin » u » v; adj[u].push_back(v); adj[v].push_back(u); } // 构建树结构，确定父子关系 vector parent(n + 1, 0); vector> children(n + 1); queue q; vector visited(n + 1, false); q.push(1); visited[1] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; parent[v] = u; children[u].push_back(v); q.push(v); } } } int m; cin » m; unordered_set bomb_set; for (int i = 0; i < m; ++i) { int b; cin » b; bomb_set.insert(b); } vector has_bomb(n + 1, false); for (int b : bomb_set) has_bomb[b] = true; // 标记核弹节点 // 后序遍历标记所有包含核弹的子树 stack> st; st.push({1, false}); while (!st.empty()) { auto [u, processed] = st.top(); st.pop(); if (!processed) { st.push({u, true}); // 逆序入栈以保证子节点按顺序处理 for (auto it = children[u].rbegin(); it != children[u].rend(); ++it) st.push({*it, false}); } else { for (int v : children[u]) { if (has_bomb[v]) { has_bomb[u] = true; break; // 只要有一个子节点有炸弹，父节点即标记 } } } } int ans = 0; for (int u = 1; u <= n; ++u) { // 判断是否为信号中转站：根节点或非叶子非根节点 bool is_station = (u == 1) || (!children[u].empty()); if (is_station) { int cnt = 0; for (int v : children[u]) { if (has_bomb[v]) cnt++; } ans += max(0, cnt - 1); // 需要控制器数为 cnt-1 } } cout « ans « endl; return 0; }

运行限制

代码思路解析

1. 输入处理与树构建 通过邻接表存储树结构，并用BFS确定父子关系，构建每个节点的子节点列表。
2. 核弹标记 标记所有含有核弹的叶子节点。
3. 后序遍历标记子树 从叶子节点向上回溯，标记每个节点的子树是否包含核弹。若某节点的子节点子树包含核弹，则该节点也被标记。
4. 统计控制器数量 遍历每个信号中转站节点，统计其子节点中包含核弹的数目。若数目超过1，则需在该节点安装（数目-1）个控制器，确保信号正确传输。

关键点

• 信号中转站判断 ：根节点或非叶子节点。
• 后序遍历更新子树标记 ：确保父节点正确反映子树的核弹状态。
• 控制器计算 ：每个中转站需要控制器数为其包含核弹子节点数减一，确保最少干预。

题目详细解析

我们用一个具体例子理解题目： 样例输入 ： 5 1 2 1 3 1 4 2 5 2 4 5 

关键逻辑

1. 信号传播规则 ：

• 中转站（非叶子非根节点）默认随机选择一个子节点。
• 安装控制器后，中转站可以指定信号传递方向。

2. 核心观察 ：

• 如果某个中转站的多个子节点的子树包含核弹，必须强制信号走向这些子节点。
• 控制器的作用是减少选择的不确定性，确保覆盖所有核弹。

3. 解决方案 ：

• 统计每个中转站节点需要引导的子节点数量。
• 若某中转站有 k 个子节点的子树含核弹，则需 k-1 个控制器。

代码分步解析

1 邻接表构建与树的遍历

邻接表是树的标准存储方式，每个节点存储其直接连接的节点： vector> adj(n + 1); for (int i = 0; i < n - 1; ++i) { int u, v; cin » u » v; adj[u].push_back(v); adj[v].push_back(u); } 通过BFS构建树的父子关系： queue q; q.push(1); visited[1] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; parent[v] = u; children[u].push_back(v); // 建立子节点列表 q.push(v); } } }

2 后序遍历标记子树

通过后序遍历标记每个节点的子树是否含核弹： stack> st; st.push({1, false}); while (!st.empty()) { auto [u, processed] = st.top(); st.pop(); if (!processed) { st.push({u, true}); // 逆序入栈以保证处理顺序 for (auto it = children[u].rbegin(); it != children[u].rend(); ++it) st.push({*it, false}); } else { for (int v : children[u]) { if (has_bomb[v]) { has_bomb[u] = true; // 子节点有核弹则标记 break; } } } } 例如，节点5的 has_bomb 为真，其父节点2的 has_bomb 也会被标记为真。

3 统计控制器数量

遍历所有中转站节点，计算需要控制器数量： int ans = 0; for (int u = 1; u <= n; ++u) { // 判断是否为中转站 bool is_station = (u == 1) || (!children[u].empty()); if (is_station) { int cnt = 0; for (int v : children[u]) { if (has_bomb[v]) cnt++; } ans += max(0, cnt - 1); // 关键计算 } }

• 根节点1 ：子节点2和4的子树含核弹 → cnt=2 → 贡献 1。
• 节点2 ：子节点5的子树含核弹 → cnt=1 → 贡献 0。
• 总控制器数为 1。

邻接表与树构建示例

假设输入边为 1-2, 1-3, 1-4, 2-5，邻接表如下： 1: [2,3,4] 2: [1,5] 3: [1] 4: [1] 5: [2] 通过BFS得到的父子关系： 1的子节点：2,3,4 2的子节点：5 3的子节点：无 4的子节点：无 5的子节点：无

总结

• 邻接表 ：存储图结构，每个节点维护相邻节点列表。
• 树构建 ：通过BFS确定父子关系，明确树形结构。
• 后序遍历 ：自底向上标记子树状态，确保父节点能继承子节点的核弹信息。
• 控制器计算 ：每个中转站需要覆盖的子节点数决定控制器数量。