前言
先贴一道模板题 Luogu 2495
题意，给你一棵n个点的有边权树，有m次询问，每次询问k个点，要删除一些边使得这k个点均不与1号点联通。
数据范围：$2\le n\le250000,m\ge1,\sum k_i\le500000,1\le ki\le n-1$；
考虑树形dp1
2
3
4
5
6
7
8
9
10
11
12
13
14LL get_ans(int u){
bool leaf=1;
LL ret=0;
for (int p=head[u];p;p=nxt[p]){
ret+=get_ans(a[p]);
leaf=0;
}
head[u]=0;
if (del[u]){
del[u]=0;
return ff[u];
}
return min(ret,1ll*ff[u]);
}
ff表示我连向我父亲的边的边权。
我是直接暴力dfs一遍，如果我这个点要删除，那么一定是删我的ff边最优。
否则选择删我ff边或者一个一个删我的子节点
这样dp一遍是O(n)的，但是m次询问就T了，但是注意到$\sum k$并不大，于是虚树闪亮登场了
介绍
虚树就是把原树中少量的有效节点和他们两两的lca拿出来，这样就可以去除一些无效节点，从而降低复杂度。
如果有效节点是k个，那么虚树中节点的个数是2*k个，为什么，请看下文。
实现
先讲讲如何建虚树，在本题中，虚树上的边权就是原先这条路径上边权的min，因为你要删肯定是删最小边最优。
先dfs一遍，求出基本信息。1
2
3
4
5
6
7
8
9
10
11
12void dfs(int u){
dfn[u]=++tim;
for (int p=head[u];p;p=nxt[p]){
int v=a[p];
if (v!=f[u][0]){
f[v][0]=u;
minn[v][0]=b[p];
dep[v]=dep[u]+1;
dfs(v);
}
}
}
先倍增求lca预处理好，倍增的时候最小值也处理好1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24for (int j=1;j<=20;j++){
for (int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1],
minn[i][j]=min(minn[i][j-1],minn[f[i][j-1]][j-1]);
}
int lca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
int tmp=dep[x]-dep[y];
for (int i=0;i<=20;i++){
if (tmp&(1<<i)) x=f[x][i];
}
if (x==y) return x;
for (int i=20;i>=0;i--){
if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
}
return f[x][0];
}
int dist(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
int tmp=dep[x]-dep[y],ret=1e9;
for (int i=0;i<=20;i++){
if (tmp&(1<<i)) ret=min(ret,minn[x][i]),x=f[x][i];
}
return ret;
}
然后把所有有效点按照dfn值排序，每次新加入一个节点，他最多会和前面的一个节点产生一个lca。
简单证明一下，
设当前加入的节点x，与y节点产生了一个新的lca,lca1。
假设x还与z产生了一个新的lca,lca2，不妨假设dep[lca2]>dep[lca1] (不然交换y,z即可）
那么z,y的lca必定为lca1，所以假设不成立
这样我们就证明了虚树中节点个数是min(n,2*k)个的。
构建虚树
维护一个栈，表示从根到栈顶元素的这条链
我们新加入一个节点记为x，链的末端，即栈顶，为p，lca为lca(x,p)，
有两种情况:
1.p和x分立在lca的两棵子树下.
2.lca是p.
为什么lca不能是x?
因为如果lca是x,说明dfn[lca]=dfn[x]$ < $dfn[p],而我们是按照dfs序号遍历的,于是dfn[p]$ <$dfn[x],矛盾.)
对于第二种情况,直接在栈中插入节点x即可,不要连接任何边(后面会说为什么).
对于第一种情况,要仔细分析.
我们是按照dfn遍历的(因为很重要所以多说几遍……),有dfn[x]>dfn[p]>dfn[lca].
这说明什么呢? 说明一件很重要的事:我们已经把lca所引领的子树中,p所在的子树全部遍历完了!
简略的证明:如果没有遍历完,那么肯定有一个未加入的点h,满足dfn[h]$ <$dfn[x],
我们按照dfs序号递增顺序遍历的话,应该把h加进来了才能考虑x.
这样,我们就直接构建lca引领的,p所在的那个子树. 我们在退栈的时候构建子树.
p所在的子树如果还有其它部分,它一定在之前就构建好了(所有退栈的点都已经被正确地连入树中了),就剩那条链.
如何正确地把p到lca那部分连进去呢?
设栈顶的节点为p,栈顶第二个节点为q.
重复以下操作:
如果dfn[q]>dfn[lca],可以直接连边$q\to p$,然后退一次栈.
如果dfn[q]=dfn[lca],说明q=lca,直接连边$lca\to p$,此时子树已经构建完毕.
如果dfn[q]<dfn[lca],说明lca被p与q夹在中间,此时连边$lca\to p$,退一次栈,再把lca压入栈.此时子树构建完毕
最后,为了维护dfs链,要把x压入栈. 整个过程就是这样
上面这个讨论的过程来自chenhuan001的博客，把一些有小错误的地方改正了，我就是看着这个学会的，讲的非常清楚。
还不明白的可以结合代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17void insert(int x){
if (!top){
st[++top]=x;
return;
}
int ll=lca(st[top],x);
while (dep[st[top-1]]>dep[ll]&&top>1){
add(st[top-1],st[top],dist(st[top-1],st[top]));
top--;
}
if (dep[ll]<dep[st[top]]){
add(ll,st[top],dist(ll,st[top]));
top--;
}
if (!top||dep[st[top]]<dep[ll]) st[++top]=ll;
st[++top]=x;
}
那我们把虚树建出来后，用最前面讲的dp跑一边就好了。
好了,以上就是我个人对虚树的一些理解，希望可以帮助大家学习，如果还有疑问可以给我留言，或者到我好友的博客看更详细的代码和建树过程的描述。
https://blog.csdn.net/zhouyuheng2003/article/details/79110326
谢谢。