2161 字
11 分钟
虚树

虚树#

题目重述#

给定一棵以 11 为根的树,并有多次独立询问;第 ii 次询问给出关键点集合 SiS_i。

  • CF613D:可删除非关键点,使任意两个关键点不连通;求最少删除点数。若存在两关键点在原树上相邻,则无解。
  • P2495:边有正权。可删除若干边,使根 11 不可达任何关键点;求最小删除边权和。

两题中,单次询问的 ∣Si∣|S_i| 很小,但 nn 与询问总规模很大。若每次在整棵树上 DP,复杂度会退化为 O(nq)O(nq)。

关键观察#

虚树仅需保留关键节点与分叉点#

把关键点按 DFS 序排列,对相邻关键点求 LCA,并将这些 LCA 与根一同加入。得到的点集按 DFS 序建树,称为虚树。

任意两关键点的路径,其分叉位置必为若干关键点的 LCA;若一个原树节点既不是关键点,也不是这些 LCA,则它只处于某条不发生分叉的祖先链内部。该链上的节点对于不同关键点子树没有独立的组合关系,故可压缩成一条虚边而不改变可行解与最优值。

排序后只补相邻节点的 LCA 已足够:设 u,vu,v 是 DFS 序相邻的关键点,某个需要保留的分叉点 xx 的不同子树中存在关键点;这些子树在 DFS 序中形成连续区间,其边界处必出现一对相邻关键点跨越 xx,于是 x=operatornameLCA(u,v)x=operatorname{LCA}(u,v)。

关键点与 LCA

虚树大小是线性的#

对 kk 个关键点,补入的 LCA 不超过 k−1k-1 个;再加入根后,虚树节点数为 O(k)O(k)。因此一次询问可只在 O(k)O(k) 个节点上做 DP。

CF613D 的相邻关键点判定#

若关键点 uu 的父亲 p(u)p(u) 也是关键点,则原树边 (p(u),u)(p(u),u) 的两个端点均不可删,且它们始终连通,故无解。反之,此情形不存在时,虚树 DP 中对每条关键点分支均能在其首个可删位置切断,后述转移可构造可行方案。

解析#

预处理#

从根 DFS 得到 operatornamedfnoperatorname{dfn}、深度 operatornamedepoperatorname{dep}、二进制祖先 operatornamefaoperatorname{fa}。P2495 还维护

mn[u]=min⁡{w(e)∣e 在根到 u 的路径上}。mn[u]=\min\{w(e)\mid e\text{ 在根到 }u\text{ 的路径上}\}。

这是因为若决定从根侧隔离整个 uu 的原树子树,在根到 uu 的链上任选一条边切断均可,最优代价就是该路径最小边权 mn[u]mn[u]。

建树:DFS 序与单调栈#

将本次关键点按 operatornamedfnoperatorname{dfn} 排序,栈中维持尚未确定父亲的「根到当前点」祖先链。依次处理新关键点 vv,令 l=operatornameLCA(extstack.top,v)l=operatorname{LCA}( ext{stack.top},v):

  1. 当栈中倒数第二个节点深度不小于 operatornamedep[l]operatorname{dep}[l] 时,栈顶节点的虚树父亲已经确定;连边并弹栈。
  2. 若 ll 不在栈顶,连 l→stack.topl\to\text{stack.top},将栈顶替换为 ll。
  3. 将 vv 入栈。全部处理后,将剩余栈逐个连边弹出。

栈内节点深度严格递增,每个节点至多入栈、出栈各一次;建树复杂度为 O(klog⁡n)O(k\log n),其中 LCA 查询使用倍增。

单调栈连边完成的虚树

CF613D:最少删除点数#

令 cnt[u]cnt[u] 表示处理完 uu 的虚树子树后,是否仍有一个尚未与上方隔离的关键点分支。后序遍历:

  • 若 uu 是关键点,则不能删 uu。对每个孩子 vv,若 cnt[v]=1cnt[v]=1,必须在 uu 与该分支之间切断一个点,答案加一,并令该分支归零;最后令 cnt[u]=1cnt[u]=1。
  • 若 uu 不是关键点,合并所有 cnt[v]cnt[v]。若合并后至少有两个未隔离分支,则这些分支会经 uu 互相连通,删除 uu 一次即可同时切断它们,答案加一并令 cnt[u]=0cnt[u]=0;否则保留唯一分支向上。

第二条转移是最优的:当至少两个分支上行时,任何可行方案都必须切断它们在 uu 处的汇合;删 uu 花费 11 且一次完成。关键点不能删时,只能分别切断各个仍携带关键点的孩子分支。

CF613D 与 P2495 的 DP 分支

P2495:最小割边代价#

令 f[u]f[u] 为使虚树中 uu 的子树不含与 uu 连通的关键点的最小代价。若 uu 是虚树叶子,必为关键点,f[u]=mn[u]f[u]=mn[u]。对内部点:

f[u]=min⁡(mn[u],∑v∈son(u)f[v]).f[u]=\min\left(mn[u],\sum_{v\in son(u)}f[v]\right).

第一项是在根到 uu 的原树路径上切一条最便宜的边,一次隔离整个子树;第二项是不切上方路径,分别处理每个虚树孩子。二者穷尽了最优解在 uu 处「整体切断」与「保留后分治」的两类选择,故取最小值正确。根的 mn[1]=+inftymn[1]=+infty,最终答案为 f[1]f[1]。

一次询问的排序、建树与 DP 复杂度为 O(klog⁡n)O(k\log n),额外空间为 O(k)O(k);树上预处理复杂度为 O(nlog⁡n)O(n\log n)。

代码#

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;
}
虚树
https://sanzenin.top/posts/obsidian/虚树/
作者
Sanzenin 凪
发布于
2026-11-16
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取