对每次能源点集合构建虚树，压缩边权取原路径最小边权，再做树形 DP 求最小切断代价。
OJ: luogu
题目 ID: P2495
难度:省选/NOI-
标签:虚树树形DPLCA树
日期: 2026-06-22 22:53
题意
给定一棵以 1 为根的带权树。每次询问给出若干个能源点，需要炸毁一些边，使根 1 无法到达任何能源点，并使总代价最小。
每次询问独立。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：在原树上直接 DP，每次询问 O(n)，用于小数据对拍。
const int MAXN = 505;
const long long INF = (1LL << 60);
struct Edge {
int to, w;
};
int n, query_count;
vector<Edge> graph_edges[MAXN];
bool is_key[MAXN];
long long dfs_solve(int u, int parent) {
if (is_key[u]) {
return INF;
}
long long answer = 0;
for (int i = 0; i < (int)graph_edges[u].size(); i++) {
int v = graph_edges[u][i].to;
int w = graph_edges[u][i].w;
if (v == parent) {
continue;
}
long long child_cost = dfs_solve(v, u);
if (child_cost > 0) {
answer += min(child_cost, (long long)w);
}
}
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
graph_edges[u].push_back({v, w});
graph_edges[v].push_back({u, w});
}
cin >> query_count;
for (int qi = 1; qi <= query_count; qi++) {
int k;
cin >> k;
vector<int> nodes(k);
for (int i = 0; i < k; i++) {
cin >> nodes[i];
is_key[nodes[i]] = true;
}
cout << dfs_solve(1, 0) << '\n';
for (int i = 0; i < k; i++) {
is_key[nodes[i]] = false;
}
}
return 0;
}暴力做法是每次在整棵树上 DP，但询问很多，不能每次遍历 n 个点。
一次询问真正有用的点只有能源点、根，以及它们之间的必要 LCA。把这些点按原树祖先关系连起来，就是虚树。
虚树中一条边 u -> v 代表原树上从 u 到 v 的一段路径。若决定在这段路径中切一条边，显然应该切代价最小的那条。因此虚树边权是原树路径上的最小边权。
建虚树流程：
- 把本次能源点按 DFS 序排序；
- 加入相邻能源点的 LCA；
- 加入根
1； - 再按 DFS 序排序去重；
- 用单调栈连接父子虚树边。
虚树 DP：
- 如果子节点是能源点，必须在父子压缩路径上切断，代价为这条虚树边权；
- 如果子节点不是能源点，可以切掉这条虚树边，也可以保留它并在子树内部切，取较小值。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250005;
const int LOG = 20;
const long long INF = (1LL << 60);
int n, query_count;
int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], edge_weight[MAXN * 2], edge_cnt;
int depth_node[MAXN], dfn[MAXN], tout[MAXN], timer_dfn;
int up[MAXN][LOG + 1];
int min_up[MAXN][LOG + 1]; // min_up[x][j] 表示 x 向上跳 2^j 步路径上的最小边权。
int virtual_head[MAXN], virtual_to[MAXN], virtual_nxt[MAXN], virtual_weight[MAXN], virtual_cnt;
bool is_key[MAXN]; // 当前询问中的能源点标记。
long long dp[MAXN]; // 虚树 DP：从该点向下切断所有能源点的最小代价。
void add_edge(int u, int v, int w) {
edge_cnt++;
to[edge_cnt] = v;
edge_weight[edge_cnt] = w;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void add_virtual_edge(int u, int v, int w) {
virtual_cnt++;
virtual_to[virtual_cnt] = v;
virtual_weight[virtual_cnt] = w;
virtual_nxt[virtual_cnt] = virtual_head[u];
virtual_head[u] = virtual_cnt;
}
void read_tree() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
add_edge(u, v, w);
add_edge(v, u, w);
}
}
void build_lca() {
static int iter_edge[MAXN];
static int stack_node[MAXN];
for (int i = 1; i <= n; i++) {
iter_edge[i] = head[i];
}
int top = 1;
stack_node[top] = 1;
depth_node[1] = 1;
min_up[1][0] = (int)1e9;
dfn[1] = ++timer_dfn;
// 迭代 DFS 生成 dfn/tout，避免 25 万深度时递归爆栈。
while (top > 0) {
int u = stack_node[top];
int &edge_id = iter_edge[u];
if (edge_id == 0) {
tout[u] = timer_dfn;
top--;
continue;
}
int current_edge = edge_id;
edge_id = nxt[edge_id];
int v = to[current_edge];
if (v == up[u][0]) {
continue;
}
up[v][0] = u;
min_up[v][0] = edge_weight[current_edge];
depth_node[v] = depth_node[u] + 1;
for (int j = 1; j <= LOG; j++) {
up[v][j] = up[up[v][j - 1]][j - 1];
min_up[v][j] = min(min_up[v][j - 1], min_up[up[v][j - 1]][j - 1]);
}
dfn[v] = ++timer_dfn;
iter_edge[v] = head[v];
stack_node[++top] = v;
}
}
bool is_ancestor(int x, int y) {
return dfn[x] <= dfn[y] && tout[y] <= tout[x];
}
int lca(int x, int y) {
if (is_ancestor(x, y)) {
return x;
}
if (is_ancestor(y, x)) {
return y;
}
for (int j = LOG; j >= 0; j--) {
if (up[x][j] != 0 && !is_ancestor(up[x][j], y)) {
x = up[x][j];
}
}
return up[x][0];
}
int min_edge_on_path(int x, int y) {
int answer = (int)1e9;
if (depth_node[x] < depth_node[y]) {
swap(x, y);
}
int diff = depth_node[x] - depth_node[y];
for (int j = LOG; j >= 0; j--) {
if ((diff & (1 << j)) != 0) {
answer = min(answer, min_up[x][j]);
x = up[x][j];
}
}
if (x == y) {
return answer;
}
for (int j = LOG; j >= 0; j--) {
if (up[x][j] != up[y][j]) {
answer = min(answer, min_up[x][j]);
answer = min(answer, min_up[y][j]);
x = up[x][j];
y = up[y][j];
}
}
answer = min(answer, min_up[x][0]);
answer = min(answer, min_up[y][0]);
return answer;
}
bool cmp_dfn(int x, int y) {
return dfn[x] < dfn[y];
}
long long solve_one_query(vector<int> &key_nodes) {
vector<int> nodes = key_nodes;
sort(nodes.begin(), nodes.end(), cmp_dfn);
int original_size = (int)nodes.size();
for (int i = 0; i + 1 < original_size; i++) {
nodes.push_back(lca(nodes[i], nodes[i + 1]));
}
nodes.push_back(1);
sort(nodes.begin(), nodes.end(), cmp_dfn);
nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
for (int i = 0; i < (int)nodes.size(); i++) {
virtual_head[nodes[i]] = 0;
dp[nodes[i]] = 0;
}
virtual_cnt = 0;
// 单调栈建虚树：相邻虚树节点之间的边权为原树路径上的最小边权。
vector<int> stack_nodes;
for (int i = 0; i < (int)nodes.size(); i++) {
int x = nodes[i];
while (!stack_nodes.empty() && !is_ancestor(stack_nodes.back(), x)) {
stack_nodes.pop_back();
}
if (!stack_nodes.empty()) {
int parent = stack_nodes.back();
add_virtual_edge(parent, x, min_edge_on_path(parent, x));
}
stack_nodes.push_back(x);
}
// 虚树 DP：对每个子树，要么切掉连接父亲的这条路径，要么继续在子树内部切。
for (int i = (int)nodes.size() - 1; i >= 0; i--) {
int u = nodes[i];
long long sum = 0;
for (int e = virtual_head[u]; e != 0; e = virtual_nxt[e]) {
int v = virtual_to[e];
long long cut_cost = virtual_weight[e];
if (is_key[v]) {
sum += cut_cost;
} else {
sum += min(dp[v], cut_cost);
}
}
dp[u] = sum;
}
return dp[1];
}
void solve() {
build_lca();
cin >> query_count;
for (int qi = 1; qi <= query_count; qi++) {
int k;
cin >> k;
vector<int> key_nodes(k);
for (int i = 0; i < k; i++) {
cin >> key_nodes[i];
is_key[key_nodes[i]] = true;
}
cout << solve_one_query(key_nodes) << '\n';
for (int i = 0; i < k; i++) {
is_key[key_nodes[i]] = false;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_tree();
solve();
return 0;
}复杂度
预处理
一次询问若有 k 个能源点，复杂度约为
空间复杂度为
总结
虚树的价值是把一次询问压缩到关键点规模。
本题还要注意虚树边权不是路径长度，而是原路径上的最小边权，因为这代表切断这段路径的最低代价。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
