虚树
虚树
开个新坑，差点暴毙，开心。
-
虚树是什么？
虚树，顾名思义就是不真实的树，它出现在一类树形DP问题中。当你发现一道题目是在树上搞事情，多组询问、并且无法用树上莫队这种数据结构暴力维护、\(\sum k\)为多少时，恭喜你，这是一道虚树题。现在为了了解它，我们从一道经典虚树问题开始。
-
题目大意
给出一棵树，每条边有一个边权。
有m次询问，每次询问给定k个点，问：让这k个点都不与1号点连通的最小代价。
\(n\leq 250000,m\geq 1,\sum k\leq 500000\)(m是数据组数)。
-
暴力dp
- 每一个虚树问题首先都是一个树形DP问题，所以我们先要考虑只有一组询问的时候，怎么做树形dp。
- 对于这道题来说，我们如果把这k个点和可能会影响答案的其他一些点找出来，就能很快的dp维护答案。并且我们发现\(\sum k\)是比较小的，思路确实是朝着正确的方向的。
-
思想
- 其实你发现，对于答案可能产生影响的点只有给定的k个点与相邻点的lca。
- 因此关键在于我们如何将这些点都快速的找到并且建出一棵树来。
-
构造方法
- 首先，对整棵树dfs一遍，求出点的dfs序。每次把询问点按照dfs序从小到大排序。
- 同时维护一个栈，表示从根节点到栈顶元素这条链。
- 假设当前要假如x，那么我们找与它相邻点的lca。也就是先另lca=LCA（x，s[top]）。显然会有两种情况：
- 一个是s[top]是x的祖先，那么lca=s[top]，这时候你显然直接将x入栈就好了。
- x，s[top]在lca的两颗子树上，那么s[top]这颗子树肯定处理完了，因为是按照dfs序处理点的。因此，我们可以判断当前栈顶的点是不是离lca最近的点，如果不是，就将s[top]与s[top-1]连边，然后不断弹出栈顶，否则就将lca与s[top]连边，然后弹出栈顶，将lca入栈。最后再将x入栈。
- 如果觉得有什么疑惑的话，可以拿张图试试，你会发现这样的构造方法确实是可以构造出我们所要的“虚树” 的。
- 那么本题就差不多做完了，直接在虚树上dp就好。
Coding
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int N=5e5+10;
int n,m,tot,num,top,k,ver[N],Next[N],lin[N],edge[N],dfn[N],h[N],s[N],mn[N],dep[N],f[N/2][35];
vector<int>son[N];
int read(){
char ch=getchar();int num=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){num=(num<<1)+(num<<3)+(ch^48);ch=getchar();}
return num*f;
}
void add(int x,int y,int z){ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;edge[tot]=z;}
void add_c(int x,int y){son[x].push_back(y);}
bool cmp(int a,int b){return dfn[a]<dfn[b];}
void dfs(int x,int fa){
f[x][0]=fa;dfn[x]=++num;dep[x]=dep[fa]+1;
for(int i=1;i<=30;++i) f[x][i]=f[f[x][i-1]][i-1];
for(int i=lin[x];i;i=Next[i]){
int y=ver[i];
if(y==fa) continue;
mn[y]=min(mn[x],edge[i]);
dfs(y,x);
}
}
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=30;i>=0;--i){
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
}
if(x==y) return x;
for(int i=30;i>=0;--i){
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
}
return f[x][0];
}
void insert(int x){
if(top==1){
s[++top]=x;return ;
}
int p,lca;
p=s[top];lca=LCA(p,x);
if(lca==p){
return;
}
while(top>1&&dfn[s[top-1]]>=dfn[lca]){
add_c(s[top-1],s[top]);top--;
}
if(lca!=s[top]) add_c(lca,s[top]),s[top]=lca;
s[++top]=x;
}
ll dp(int x){
if(son[x].size()==0) return mn[x];
ll sum=0;
for(int i=0;i<son[x].size();++i){
sum+=dp(son[x][i]);
}
son[x].clear();
return min(1LL*mn[x],sum);
}
int main(){
n=read();
for(int i=1;i<n;++i){
int u=read(),v=read(),w=read();
add(u,v,w);add(v,u,w);
}mn[1]=1<<29;
dfs(1,0);
m=read();
while(m--){
k=read();top=0;
for(int i=1;i<=k;++i) h[i]=read();
sort(h+1,h+k+1,cmp);s[top=1]=1;
for(int i=1;i<=k;++i)
insert(h[i]);
while(top>0)
add_c(s[top-1],s[top]),top--;
printf("%lld\n",dp(1));
}
return 0;
}
版权声明：本文为kgxw0430原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。