题解(救援分区)
2026-10-28 21:29:04
发布于:湖南
3阅读
0回复
0点赞
先梳理题意 & 核心思路
题目是一棵树上砍一条边,把树拆成两棵子树 A、B。
要求:
- A 里面 至少 1 个医疗站、至少 1 个物资站
- B 里面 至少 1 个医疗站、至少 1 个物资站
在合法的切割里,求 (|sumA - sumB|) 的最小值;无解输出 -1。
设:
- sumAll:整棵树总人口
- (subSum[x]):以 x 为根的子树人口和
- (subM[x]):子树 x 内医疗站总数
- (subS[x]):子树 x 内物资站总数
- totalM:全树医疗站总数
- totalS:全树物资站总数
切断父节点和子节点 v 这条边后:
- 子块:子树
✅ 合法条件: - 剩下大块:原树去掉子树
✅ 合法条件:
只要同时满足上面四条,这个切割就是合法的,差值 = ,我们取最小即可。
C++代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
const ll INF = 1e18;
vector<int> g[N];
ll p[N];
int m[N], s[N];
ll subSum[N];
int subM[N], subS[N];
ll totalSum;
int totalM, totalS;
ll ans = INF;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
totalSum = 0; totalM = 0; totalS = 0;
for (int i = 1; i <= n; i++) {
cin >> p[i] >> m[i] >> s[i];
totalSum += p[i];
totalM += m[i];
totalS += s[i];
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
// 迭代后序 dfs
stack<pair<int, int>> st;
vector<bool> vis(N, false);
st.emplace(1, 0);
while (!st.empty()) {
auto [u, fa] = st.top();
if (!vis[u]) {
vis[u] = true;
subSum[u] = p[u];
subM[u] = m[u];
subS[u] = s[u];
for (int v : g[u]) {
if (v != fa) {
st.emplace(v, u);
}
}
} else {
st.pop();
for (int v : g[u]) {
if (v == fa) continue;
subSum[u] += subSum[v];
subM[u] += subM[v];
subS[u] += subS[v];
bool ok1 = (subM[v] >= 1 && subS[v] >= 1);
bool ok2 = ((totalM - subM[v]) >= 1 && (totalS - subS[v]) >= 1);
if (ok1 && ok2) {
ll diff = abs(totalSum - 2 * subSum[v]);
ans = min(ans, diff);
}
}
}
}
cout << (ans == INF ? -1 : ans) << endl;
return 0;
}
杂度说明
- ,每个点每条边遍历一次,完全满足
- 可以到 ,全部用 ,这点代码已经处理
这里空空如也






有帮助,赞一个