虚树
最近学算法都感觉越来越看不懂别人的博客了,所以决定以后学的东西多多少少都写一点总结,以前学过的也有可能会写。
声明:以下所有求
\operatorname{Part\ 1.} 引入
来看一道例题:
-
P2495 【模板】虚树 / [SDOI2011] 消耗战
- 题目大意:
有一颗n 个节点的树,边有边权。有q 次询问,每一次询问给出若干个关键点,要求删掉若干条边,使得1 不与任何关键点连通。求删掉的边权和的最小值,保证1 不是关键点,n\le2.5\times10^5 ,所有询问关键点总数\le5\times10^5 。 - 题解:
先考虑最朴素的做法,显然树形 dp。
设f_u 表示以u 为根的子树内,要求u 不与子树内任何关键点连通的答案,显然有:f_u=\sum_{v\in son(u)}\min(f_v,w) 其中
w 表示(u,v) 的边权。注意u 为关键点时f_u=+\infty 。答案即为f_u 。
- 题目大意:
\operatorname{Part\ 2.} 优化
考虑这个做法慢在那里。
显然你没必要每次把所有点都算出来。
你总共 dp 算过的点数是
有一个非常牛的想法:取出若干点,使得只 dp 这些点也可以得到正确的答案,你也可以理解为把原树中不影响答案的长链全都缩掉。
现在要求哪些点必须保留。显然关键点必须被保留。
接着观察一些性质:
- 任意两个关键点的 LCA 必须保留
这个很显然,如果\operatorname{lca}(u,v) 被删掉了,那么要么u,v 会被缩到一起,要么就连不上祖先了。 - 只要保留关键点和关键点之间两两的 LCA 就足够了
设V=S\cup\{\operatorname{LCA}(x,y)\mid x,y\in S\} ,其中S 是关键点集合。
考虑任意一个不在V 中的节点p ,显然它所有儿子里一定至多有一个儿子的子树内有关键点。
那么在 dp 中它一定会一直向上传递,不会产生任何分岔,如果有分岔也是在儿子的子树内,保留的也是在儿子子树内的点。
所以它可以直接删掉。
对于这个题因为答案是
\operatorname{Part\ 3.} 虚树的定义
由上面的证明,我们引出虚树的概念。
定义. 给定原树
- 包含
S 中所有点; - 包含
S 中任意两点的 LCA; -
-
性质.
证明:最坏情况为构造一颗二叉树,如果想深究可以继续往下看,下面的构造部分都会讲到。
所以只要我们能高效地构造出这棵虚树,就能把一次 DP 的规模从
\operatorname{Part\ 4.} 构造
先考虑怎么把所有需要的点丢进来,再考虑怎么连边。
直接
把关键点按
\operatorname{dfn} 排序后,任意两个关键点的 LCA,一定是某对相邻关键点的 LCA。
-
证明:
设u,v\in S ,令w=\operatorname{lca}(u,v) 。-
若
w\in S ,则w 本身就是关键点,已经在集合里,不用额外加入。 -
若
w\notin S ,则u,v 一定在w 的两个不同儿子的子树里。设u 在儿子a 的子树内,v 在儿子b 的子树内,a\ne b ,且\operatorname{dfn}_u<\operatorname{dfn}_v 。
把关键点按\operatorname{dfn} 排序后,从u 往后扫,必然存在第一个离开子树a 的关键点,记为y ,它前面一个关键点记为x 。于是:-
-
- 从
u 到v 的\operatorname{dfn} 区间不会离开w 的子树,所以y 仍在w 的子树内; - 因此
y 只能在w 的另一个儿子子树b 内。
所以
x\in a ,y\in b ,a\ne b ,于是\operatorname{lca}(x,y)=w. 也就是说,
w 是某一对相邻关键点的 LCA,已经被加入集合,证毕。 -
-
所以只需要加入
同样的,这个也可以解释前一部分中虚树点的数量上限,因为相邻对数量是
点选完了,接着考虑怎么把树建出来。
还是按照
处理当前点
由于按照
\operatorname{Part\ 5.} 在虚树上 DP
构造完虚树后,直接在虚树上跑原题 DP:
- 关键点:
f_u=+\infty ; - 非关键点:
f_u=\sum_{v\in son_{\text{虚}}(u)}\min(f_v,\ w_{\text{虚}}(u,v)) 。
其中
有前面的证明可知这是等价的,但是时间复杂度边为
综合一下,虚树解决整个问题的时间复杂度降至了
非常建议看一下代码,不要只听想法不会实现了。
:::success[P2495 【模板】虚树 / [SDOI2011] 消耗战 Code] 感觉还是比较好写的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lg = 19;
const ll inf = 1e18;
const int N = 2.5e5 + 5;
int n, m, k;
ll minx[lg][N];
int cnt, dfn[N], dep[N];
int st[lg][N], up[lg][N];
vector<pair<int, int>> g[N];
int get(int x, int y)
{
return dep[x] < dep[y] ? x : y;
}
int lca(int u, int v)
{
if(u == v) return u;
u = dfn[u], v = dfn[v];
if(u > v) swap(u, v);
int k = __lg(v - u++);
return up[0][get(st[k][u], st[k][v - (1 << k) + 1])];
}
ll getmin(int u, int v)
{
ll res = inf;
for(int i = lg - 1; i >= 0; i--)
{
if(dep[up[i][v]] >= dep[u]) res = min(res, minx[i][v]), v = up[i][v];
}
return res;
}
struct VirtualTree
{
ll f[N];
bool vis[N];
vector<int> nodes;
int top, fa[N], stk[N];
void build(vector<int> vec)
{
nodes = vec;
for(auto x : nodes) vis[x] = 1;
sort(nodes.begin(), nodes.end(), [&](int x, int y)
{
return dfn[x] < dfn[y];
});
int m = nodes.size();
for(int i = 0; i + 1 < m; i++) nodes.push_back(lca(nodes[i], nodes[i + 1]));
nodes.push_back(1);
sort(nodes.begin(), nodes.end(), [&](int x, int y)
{
return dfn[x] < dfn[y];
});
nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
top = 0, stk[++top] = 1;
for(auto u : nodes)
{
if(u == 1) continue;
int l = lca(u, stk[top]);
while(dep[stk[top - 1]] >= dep[l]) fa[stk[top]] = stk[top - 1], top--;
stk[++top] = u;
}
while(top > 1) fa[stk[top]] = stk[top - 1], top--;
return;
}
ll solve()
{
for(auto u : nodes) f[u] = 0;
for(int i = nodes.size() - 1, u; i >= 0; i--)
{
u = nodes[i];
if(vis[u]) f[u] = inf;
f[fa[u]] += min(f[u], getmin(fa[u], u));
}
return f[1];
}
void clear()
{
for(auto u : nodes) vis[u] = 0;
nodes.clear();
return;
}
}tr;
void dfs(int u, int fa, int w)
{
dfn[u] = ++cnt, dep[u] = dep[fa] + 1;
up[0][u] = fa, st[0][cnt] = u, minx[0][u] = w;
for(int i = 1; i < lg; up[i][u] = up[i - 1][up[i - 1][u]], minx[i][u] = min(minx[i - 1][u], minx[i - 1][up[i - 1][u]]), i++);
for(auto [v, w] : g[u])
{
if(v == fa) continue;
dfs(v, u, w);
}
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
cin >> n;
for(int i = 1, u, v, w; i < n; i++)
{
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
for(int i = 0; i < lg; minx[i][0] = inf, i++);
dfs(1, 0, inf);
for(int j = 1; j < lg; j++)
{
for(int i = 1; i + (1 << j) - 1 <= n; st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]), i++);
}
cin >> m;
while(m--)
{
cin >> k;
tr.clear();
vector<int> vec;
vec.reserve(k);
for(int i = 1, x; i <= k; i++) cin >> x, vec.push_back(x);
tr.build(vec);
cout << tr.solve() << "\n";
}
return 0;
}
:::
\operatorname{Part\ 6.} 练习
- P4103 [HEOI2014] 大工程
- P3233 [HNOI2014] 世界树
- P8877 [传智杯 #5 初赛] I-不散的宴会