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

问题描述

危机纪元 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 个整数，表示具有核弹起爆装置的节点编号。

输出格式

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

样例输入

样例输出

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;vector<vector<int>> 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<int> parent(n + 1, 0);vector<vector<int>> children(n + 1);queue<int> q;vector<bool> 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<int> bomb_set;for (int i = 0; i < m; ++i) {int b;cin >> b;bomb_set.insert(b);}vector<bool> has_bomb(n + 1, false);for (int b : bomb_set) has_bomb[b] = true; // 标记核弹节点// 后序遍历标记所有包含核弹的子树stack<pair<int, bool>> 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;
}

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M
PyPy3	3s	256M
Go	3s	256M
JavaScript	3s	256M

代码思路解析

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

关键点

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

题目详细解析

我们用一个具体例子理解题目：

样例输入：

关键逻辑

信号传播规则：
- 中转站（非叶子非根节点）默认随机选择一个子节点。
- 安装控制器后，中转站可以指定信号传递方向。
核心观察：
- 如果某个中转站的多个子节点的子树包含核弹，必须强制信号走向这些子节点。
- 控制器的作用是减少选择的不确定性，确保覆盖所有核弹。
解决方案：
- 统计每个中转站节点需要引导的子节点数量。
- 若某中转站有 k 个子节点的子树含核弹，则需 k-1 个控制器。

代码分步解析

1. 邻接表构建与树的遍历

邻接表是树的标准存储方式，每个节点存储其直接连接的节点：

vector<vector<int>> 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<int> 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<pair<int, bool>> 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确定父子关系，明确树形结构。
后序遍历：自底向上标记子树状态，确保父节点能继承子节点的核弹信息。
控制器计算：每个中转站需要覆盖的子节点数决定控制器数量。