
虚树
题目重述
给定一棵以 为根的树,并有多次独立询问;第 次询问给出关键点集合 。
- CF613D:可删除非关键点,使任意两个关键点不连通;求最少删除点数。若存在两关键点在原树上相邻,则无解。
- P2495:边有正权。可删除若干边,使根 不可达任何关键点;求最小删除边权和。
两题中,单次询问的 很小,但 与询问总规模很大。若每次在整棵树上 DP,复杂度会退化为 。
关键观察
虚树仅需保留关键节点与分叉点
把关键点按 DFS 序排列,对相邻关键点求 LCA,并将这些 LCA 与根一同加入。得到的点集按 DFS 序建树,称为虚树。
任意两关键点的路径,其分叉位置必为若干关键点的 LCA;若一个原树节点既不是关键点,也不是这些 LCA,则它只处于某条不发生分叉的祖先链内部。该链上的节点对于不同关键点子树没有独立的组合关系,故可压缩成一条虚边而不改变可行解与最优值。
排序后只补相邻节点的 LCA 已足够:设 是 DFS 序相邻的关键点,某个需要保留的分叉点 的不同子树中存在关键点;这些子树在 DFS 序中形成连续区间,其边界处必出现一对相邻关键点跨越 ,于是 。

虚树大小是线性的
对 个关键点,补入的 LCA 不超过 个;再加入根后,虚树节点数为 。因此一次询问可只在 个节点上做 DP。
CF613D 的相邻关键点判定
若关键点 的父亲 也是关键点,则原树边 的两个端点均不可删,且它们始终连通,故无解。反之,此情形不存在时,虚树 DP 中对每条关键点分支均能在其首个可删位置切断,后述转移可构造可行方案。
解析
预处理
从根 DFS 得到 、深度 、二进制祖先 。P2495 还维护
这是因为若决定从根侧隔离整个 的原树子树,在根到 的链上任选一条边切断均可,最优代价就是该路径最小边权 。
建树:DFS 序与单调栈
将本次关键点按 排序,栈中维持尚未确定父亲的「根到当前点」祖先链。依次处理新关键点 ,令 :
- 当栈中倒数第二个节点深度不小于 时,栈顶节点的虚树父亲已经确定;连边并弹栈。
- 若 不在栈顶,连 ,将栈顶替换为 。
- 将 入栈。全部处理后,将剩余栈逐个连边弹出。
栈内节点深度严格递增,每个节点至多入栈、出栈各一次;建树复杂度为 ,其中 LCA 查询使用倍增。


CF613D:最少删除点数
令 表示处理完 的虚树子树后,是否仍有一个尚未与上方隔离的关键点分支。后序遍历:
- 若 是关键点,则不能删 。对每个孩子 ,若 ,必须在 与该分支之间切断一个点,答案加一,并令该分支归零;最后令 。
- 若 不是关键点,合并所有 。若合并后至少有两个未隔离分支,则这些分支会经 互相连通,删除 一次即可同时切断它们,答案加一并令 ;否则保留唯一分支向上。
第二条转移是最优的:当至少两个分支上行时,任何可行方案都必须切断它们在 处的汇合;删 花费 且一次完成。关键点不能删时,只能分别切断各个仍携带关键点的孩子分支。

P2495:最小割边代价
令 为使虚树中 的子树不含与 连通的关键点的最小代价。若 是虚树叶子,必为关键点,。对内部点:
第一项是在根到 的原树路径上切一条最便宜的边,一次隔离整个子树;第二项是不切上方路径,分别处理每个虚树孩子。二者穷尽了最优解在 处「整体切断」与「保留后分治」的两类选择,故取最小值正确。根的 ,最终答案为 。
一次询问的排序、建树与 DP 复杂度为 ,额外空间为 ;树上预处理复杂度为 。
代码
CF613D
#include <bits/stdc++.h>#include <cstdlib>#define ll long long#define N 100005#define pr pair<ll, ll>using namespace std;ll n, ans, m, cnt, tol, q;int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); cin >> n; vector<vector<int>> adj(n + 5); for (int i = 1; i < n; i++) { ll a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } vector<int> dep(n + 5, 0); vector<int> dfn(n + 5, 0); vector<vector<int>> fa(n + 5, vector<int>(25, 0)); auto dfs = [&](auto &&self, int x, int f, auto &&tim) -> void { dfn[x] = ++tim; fa[x][0] = f; dep[x] = dep[f] + 1; for (int i = 1; i <= 20; i++) { fa[x][i] = fa[fa[x][i - 1]][i - 1]; } for (auto v : adj[x]) { if (v == f) continue; self(self, v, x, tim); } }; dfs(dfs, 1, 0, 0); auto lca = [&](ll x, ll y) -> ll { if (dep[x] < dep[y]) swap(x, y); for (int i = 20; i >= 0; i--) { if (dep[fa[x][i]] >= dep[y]) x = fa[x][i]; } if (x == y) return x; for (int i = 20; i >= 0; i--) { if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; } return fa[x][0]; }; vector<ll> h(n + 5, -1); vector<ll> cnt(n + 5, 0); vector<bool> iscri(n + 5, 0); vector<pr> edges;#define next first#define to second cin >> q; while (q--) { ll k; cin >> k; vector<int> cri(k + 5, 0); for (int i = 1; i <= k; i++) { cin >> cri[i]; iscri[cri[i]] = 1; cnt[cri[i]] = 1; } sort(cri.begin() + 1, cri.begin() + k + 1, [&](ll a, ll b) { return dfn[a] < dfn[b]; }); auto build = [&]() { auto add = [&](ll a, ll b) { auto tmp = h[a]; h[a] = edges.size(); edges.push_back({tmp, b}); }; edges.clear(); vector<int> sta; sta.push_back(1); if (cri[1] != 1) sta.push_back(cri[1]); for (int i = 2; i <= k; i++) { auto l = lca(sta.back(), cri[i]); // 递归处理lca下方的链 while (sta.size() > 1 && dep[sta[sta.size() - 2]] >= dep[l]) { add(sta[sta.size() - 2], sta.back()); sta.pop_back(); } // 如果lca不在栈中 if (l != sta.back()) { add(l, sta.back()); sta.pop_back(); sta.push_back(l); } sta.push_back(cri[i]); } while (sta.size() > 1) { add(sta[sta.size() - 2], sta.back()); sta.pop_back(); } }; build(); int flag = 0; for (int i = 1; i <= k; i++) { if (iscri[fa[cri[i]][0]]) { flag = 1; break; } } ll ans = 0; auto done = [&](auto &&self, int x) -> void { for (int i = h[x]; ~i; i = edges[i].next) { auto v = edges[i].to; self(self, v); } iscri[x] = 0; h[x] = -1; cnt[x] = 0; }; if (flag) { cout << -1 << '\n'; done(done, 1); continue; } auto dp = [&](auto &&self, int x) -> void { if (iscri[x]) { for (int i = h[x]; ~i; i = edges[i].next) { auto v = edges[i].to; self(self, v); if (cnt[v]) { ans++; cnt[v] = 0; } } } else { for (int i = h[x]; ~i; i = edges[i].next) { auto v = edges[i].to; self(self, v); cnt[x] += cnt[v]; cnt[v] = 0; } if (cnt[x] > 1) ans++, cnt[x] = 0; } }; dp(dp, 1); done(done, 1); cout << ans << '\n'; } return 0;}P2495
#include <bits/stdc++.h>#include <cstdlib>#define ll long long#define N 300005#define pr pair<ll, ll>using namespace std;// vector<vector<pr>>map1;ll n, ans, m, cnt, s;int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); vector<vector<pr>> adj(N); vector<ll> dep(N, 0), dfn(N, 0); vector<vector<ll>> fa(N, vector<ll>(23, 0)); vector<ll> mn(N, 1e9); auto solve = [&]() { cin >> n; for (int i = 1; i < n; i++) { ll a, b, c; cin >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } auto dfs = [&](auto &&self, ll x, ll f, ll w) -> void { dfn[x] = ++cnt; fa[x][0] = f; mn[x] = min(w, mn[f]); dep[x] = dep[f] + 1; for (int i = 1; i <= 22; i++) { fa[x][i] = fa[fa[x][i - 1]][i - 1]; } for (auto [v, ww] : adj[x]) { if (v == f) continue; self(self, v, x, ww); } }; dfs(dfs, 1, 0, 1e18); mn[1] = 1e18; auto lca = [&](ll x, ll y) -> ll { if (dep[x] < dep[y]) swap(x, y); for (int i = 22; i >= 0; i--) { if (dep[fa[x][i]] >= dep[y]) x = fa[x][i]; } if (x == y) return x; for (int i = 22; i >= 0; i--) { if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; } return fa[x][0]; }; cin >> m; for (int i = 1; i <= n; i++) adj[i].clear(); while (m--) { ll k; cin >> k; vector<int> nodes(k + 5); for (int i = 1; i <= k; i++) { cin >> nodes[i]; } sort(nodes.begin() + 1, nodes.begin() + k + 1, [&](ll a, ll b) { return dfn[a] < dfn[b]; }); vector<int> sta; sta.push_back(1); if (nodes[1] != 1) sta.push_back(nodes[1]); for (int i = 2; i <= k; i++) { auto l = lca(nodes[i], sta.back()); if (l == sta.back()) continue; while (sta.size() > 1 && dep[sta[sta.size() - 2]] >= dep[l]) { adj[sta[sta.size() - 2]].push_back({sta.back(), 0}); sta.pop_back(); } if (l != sta.back()) { adj[l].push_back({sta.back(), 0}); sta.pop_back(); sta.push_back(l); } sta.push_back(nodes[i]); } while (sta.size() > 1) { adj[sta[sta.size() - 2]].push_back({sta.back(), 0}); sta.pop_back(); } auto dp = [&](auto &&self, int x) -> ll { if (!adj[x].size()) return mn[x]; ll sum = 0; for (auto [v, _] : adj[x]) { sum += self(self, v); } adj[x].clear(); return min(sum, (ll)mn[x]); }; cout << dp(dp, 1) << '\n'; } }; solve(); return 0;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 0 天
部分内容可能已过时