虚树总结
Alioth_
2019-02-15 20:09:12
### 虚树
有时在做树形$DP$的时候 会出现多组询问 每一组询问指定$m$个点做修改或者别的东西 **且$n$与$\sum m$同阶**
这样的话普通的树形$DP$需要$\Theta(nm)$的复杂度 肯定是过不了 这时就会用到虚树
注意$n$与$\sum m$同阶 每次只是修改$m$个点 这时候就需要用到$\Theta(\sum m)$的算法——虚树
原来的树形$DP$是在原树上$DP$ 跑一边需要$\Theta(n)$ 这样太慢了 注意到每次修改$m$个点 我们就在虚树上保留$m$个点 称为关键点 和他们的$lca$（为了连成一棵树）其他的点合并 这样每次就形成了一棵总复杂度为$\sum m$的虚树 有效地降低了复杂度
如图 红点是关键点 蓝点是$lca$
### 构建
我们先在原树上求出$dfs$序 然后把所有的关键点按照$dfs$序排序
这是我们用一个栈来维护 栈中维护一条链 每次插入时 用新点和栈顶的$lca$的$dfn$和栈中第二个点的$dfn$比较 来判断这条链有没有拐弯
若拐弯了 则说明上一个子树已经遍历完 可以构建 我们就不断弹出节点并连边 直到处理完子树 这个判断要用栈中第二个点和$lca$比较 看他是不是在$lca$下面 如果处理完了 还要判断一下子树中是否还有点 如果有 就连$lca$和它 最后把新的点加入栈即可
若没有拐弯 直接加入栈中返回就行了（等处理完这棵子树再连边）
**关键点不一定是虚树的叶子结点**
就这样
```cpp
void insert(int x)//栈中维护的是一条链！！！！！
{
int lca=LCA(s[top],x);
while(top>1&&dfn[s[top-1]]>=dfn[lca])add_edge(s[top-1],s[top]),top--;//s[top]的子树已经遍历完 可以弹出这条链使他拐弯并连s[top]子树中的边
if(lca!=s[top])add_edge(lca,s[top]),s[top]=lca;//弹完后 若栈顶不是lca 则lca一定在他上面 且他是这个子树中最后一个点 连边 加入lca
s[++top]=x;
}
```
### 一些技巧
$1$.连完边后$s[1]$即为$root$ 这个可以确定虚树的根 如果强制以什么东西为根 直接在加入$a$数组前把他加到栈里就行了
$2$.有些题一条链上的点可以合并 如果新加入的点的$lca$是$s[top]$就不用管直接$return$即可
$3$.注意每次构建虚树后要清空连的虚边 新建的边可以用一个$vector$保存 在最后一次在虚树上的$dfs$中直接$v.clear()$即可
$4$.注意虚树上的点和虚树之外的点要分别$DP$
### 例题
#### $1.P3320$寻宝游戏
这题主要是理解虚树思想 其实不用建出虚树 由于每条边遍历两遍的特殊性质 直接用一个$set$维护一下就行了
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100000+100;
struct edge{
int to,next,w;
}e[maxn<<1];
int head[maxn],tot,n,m,ans,DIS[maxn],siz[maxn],bz[maxn],fa[maxn],dfn[maxn],id,son[maxn],dep[maxn],topf[maxn];
void add(int x,int y,int z)
{
e[++tot].to=y;
e[tot].w=z;
e[tot].next=head[x];
head[x]=tot;
}
struct node{
int id;
};
bool operator <(const node a,const node b)
{
return dfn[a.id]<dfn[b.id];
}
set<node> s;
void dfs1(int x,int f)
{
siz[x]=1;
fa[x]=f;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if(y==f)continue;
dep[y]=dep[x]+1;
DIS[y]=DIS[x]+e[i].w;
dfs1(y,x);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]])son[x]=y;
}
}
void dfs2(int x,int tp)
{
topf[x]=tp;
dfn[x]=++id;
if(!son[x])return ;
dfs2(son[x],tp);
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if(y==fa[x]||y==son[x])continue;
dfs2(y,y);
}
}
inline int lca(int x,int y)
{
while(topf[x]!=topf[y])
{
if(dep[topf[x]]>dep[topf[y]])x=fa[topf[x]];
else
y=fa[topf[y]];
}
if(dep[x]<dep[y])swap(x,y);
return y;
}
inline int dis(int x,int y)
{
return DIS[x]+DIS[y]-2*DIS[lca(x,y)];
}
inline set<node>::iterator last(set<node>::iterator Pos)
{
if(Pos==s.begin())Pos=s.end();
Pos--;
return Pos;
}
inline set<node>::iterator next(set<node>::iterator Pos)
{
Pos++;
if(Pos==s.end())Pos=s.begin();
return Pos;
}
std::set<node>::iterator l,r;
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=m;i++)
{
int u;
scanf("%lld",&u);
if(s.find((node){u})!=s.end())
{
if(s.size()!=1)
{
l=r=s.find(node{u});
l=last(l),r=next(r);
ans-=dis(u,(*l).id)+dis(u,(*r).id);
ans+=dis((*l).id,(*r).id);
}
s.erase((node){u});
}
else
{
s.insert((node){u});
if(s.size()!=1)
{
l=r=s.find((node){u});
l=last(l),r=next(r);
ans+=dis(u,(*l).id)+dis(u,(*r).id);
ans-=dis((*l).id,(*r).id);
}
}
printf("%lld\n",ans);
}
}
```
#### $2.P2495$消耗战
这题也有点特殊 每次只用$DP$虚树上的点 同时建虚树时一条链上的点也可以合并 且强制以$1$为根 不够典型 但$DP$好写
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=250001;
int n,m;
struct edge{
int next,to,w,from;
}e[maxn<<1];
int head[maxn],num;
inline void add(int x,int y,int z)
{
e[++num].to=y;
e[num].from=x;
e[num].w=z;
e[num].next=head[x];
head[x]=num;
}
vector<int>v[maxn];
inline void add_edge(int x,int y)
{
v[x].push_back(y);
}
int a[maxn],dfn[maxn],top,topf[maxn],siz[maxn],son[maxn],s[maxn],fa[maxn],deep[maxn],id;
ll mn[maxn];
void dfs1(int x,int f)
{
siz[x]=1;
fa[x]=f;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if(y==f)continue;
deep[y]=deep[x]+1;
mn[y]=min(mn[x],(ll)e[i].w);
dfs1(y,x);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]])son[x]=y;
}
}
void dfs2(int x,int tp)
{
topf[x]=tp;
dfn[x]=++id;
if(!son[x])return ;
dfs2(son[x],tp);
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if(y==fa[x]||y==son[x])continue;
dfs2(y,y);
}
}
inline bool cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
int LCA(int x,int y)
{
while(topf[x]!=topf[y])
{
if(deep[topf[x]]>deep[topf[y]])x=fa[topf[x]];
else
y=fa[topf[y]];
}
if(deep[x]<deep[y])swap(x,y);
return y;
}
//此题特殊 不做模板题
void insert(int x)//栈中维护的是一条链！！！！！
{
if(top==1){s[++top]=x;return ;}
int lca=LCA(s[top],x);
if(lca==s[top])return ;//一条链上的需求点可以用第一个点替代后面的不用加入
while(top>1&&dfn[s[top-1]]>=dfn[lca])add_edge(s[top-1],s[top]),top--;//s[top]的子树已经遍历完 可以弹出这条链使他拐弯并连s[top]子树中的边
if(lca!=s[top])add_edge(lca,s[top]),s[top]=lca;//弹完后 若栈顶不是lca 则lca一定在他上面 且他是这个子树中最后一个点 连边 加入lca
s[++top]=x;
}
ll dp(int x)
{
if(!v[x].size())return mn[x];
ll sum=0;
for(int i=0;i<v[x].size();i++)
{
int y=v[x][i];
sum+=dp(y);
}
v[x].clear();
return min(sum,mn[x]);
}
int main()
{
scanf("%d",&n);
mn[1]=1ll<<60;
for(int i=1;i<n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
deep[1]=1;
dfs1(1,0);
dfs2(1,0);
scanf("%d",&m);
while(m--)
{
int k;
scanf("%d",&k);
for(int i=1;i<=k;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+k,cmp);
s[top=1]=1;
for(int i=1;i<=k;i++)insert(a[i]);
while(top>0)
add_edge(s[top-1],s[top]),top--;
cout<<dp(1)<<endl;
}
}
```
#### $3.P3233$世界树
这才是真正的模板题 ~~虽然DP实在是太恶心~~ 但所有的特点都体现了 比如虚树内外的点分别$DP$ 插入也比较正常 但是DP太傻逼了 调了一天
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=309010;
const int INF=1000010000;
typedef pair<int,int>p;
struct edge{
int next,to;
}e[maxn<<1];
int head[maxn],rt,num,fa[maxn][30];
inline void add(int x,int y)
{
e[++num].to=y;
e[num].next=head[x];
head[x]=num;
}
vector<int>v[maxn];
inline void add_edge(int x,int y){v[x].push_back(y);}
int a[maxn],n,q,bo[maxn],A[maxn],up[maxn],bel[maxn],ans[maxn],dis[maxn],dfn[maxn],top,topf[maxn],siz[maxn],son[maxn],s[maxn],deep[maxn],id;
void dfs1(int x,int f)
{
dfn[x]=++id;
siz[x]=1;
fa[x][0]=f;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if(y==f)continue;
deep[y]=deep[x]+1;
dfs1(y,x);
siz[x]+=siz[y];
}
}
//计算儿子对父亲的贡献
void dfs3(int x)//dis[x]表示在以x为根的子树内，离x最近的管辖节点到x的距离
{
if(bo[x])
bel[x]=x,dis[x]=0;//叶子结点管辖自己 一定是管辖点
else bel[x]=0,dis[x]=INF;//初值
for(int i=0;i<v[x].size();i++)
{
int y=v[x][i];
dfs3(y);
if(dis[y]+deep[y]-deep[x]<dis[x]||(dis[y]+deep[y]-deep[x]==dis[x]&&bel[x]>bel[y]&&bel[y]))
{
dis[x]=dis[y]+deep[y]-deep[x];
bel[x]=bel[y];
}
}
}
//计算父亲对儿子的贡献 因为有可能被兄弟管辖 所以dfs3先到lca dfs4再下到这个节点
void dfs4(int u,int D,int x)
{
if(D<dis[u]||(D==dis[u]&&bel[u]>x))dis[u]=D,bel[u]=x;
else D=dis[u],x=bel[u];//一直记录父亲的 否则记录父亲的bel
for(int i=0;i<v[u].size();i++)
{
dfs4(v[u][i],D+deep[v[u][i]]-deep[u],x);
}
}
//处理虚树子树中的节点归谁
void dfs5(int x)
{
ans[bel[x]]+=siz[x];
for(int i=0;i<v[x].size();i++)
{
int y=v[x][i];//x的虚树儿子
for(int j=18;j>=0;j--)
if(fa[y][j]&&deep[fa[y][j]]>deep[x])y=fa[y][j];//ans[bel[x]]要减去所有x子树中有虚树节点的子树siz 只保留没有虚树节点的子树
ans[bel[x]]-=siz[up[v[x][i]]=y];
dfs5(v[x][i]);
}
}
//现在只剩下虚树边上的被我们忽略的节点没有确定归属。
void dfs6(int x)
{
for(int i=0;i<v[x].size();i++)
{
int y=v[x][i];
if(bel[x]==bel[y]){ans[bel[x]]+=siz[up[v[x][i]]]-siz[y];dfs6(v[x][i]);continue;}
int H=deep[bel[y]]+deep[x]-dis[x];
H=H&1?H+1>>1:(bel[y]<bel[x]?H>>1:(H>>1)+1);
for(int j=18;j>=0;j--)
if(fa[y][j]&&deep[fa[y][j]]>=H)y=fa[y][j];
ans[bel[v[x][i]]]+=siz[y]-siz[v[x][i]];
ans[bel[x]]+=siz[up[v[x][i]]]-siz[y];
dfs6(v[x][i]);
}
}
void dfs7(int x)
{
up[x]=bel[x]=dis[x]=0;
for(int i=0;i<v[x].size();i++)dfs7(v[x][i]);
v[x].clear();
}
inline bool cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
inline int LCA(int x,int y)
{
if(deep[x]>deep[y])swap(x,y);//x比y浅
for(int i=18;i>=0;i--)
if(deep[fa[y][i]]>=deep[x])y=fa[y][i];
if(x==y)return x;
for(int i=18;i>=0;i--)
if(fa[y][i]!=fa[x][i])y=fa[y][i],x=fa[x][i];
return fa[x][0];
}
void insert(int x)//栈中维护的是一条链！！！！！
{
int lca=LCA(s[top],x);
while(top>1&&dfn[s[top-1]]>=dfn[lca])add_edge(s[top-1],s[top]),top--;//s[top]的子树已经遍历完 可以弹出这条链使他拐弯并连s[top]子树中的边
if(lca!=s[top])add_edge(lca,s[top]),s[top]=lca;//弹完后 若栈顶不是lca 则lca一定在他上面 且他是这个子树中最后一个点 连边 加入lca
s[++top]=x;
}
int main()
{
// freopen("10.in","r",stdin);
// freopen("new 1.ans","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
deep[1]=1;
dfs1(1,0);
for(int i=1;i<=18;i++)
for(int j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
scanf("%d",&q);
while(q--)
{
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d",&a[i]),A[i]=a[i],bo[a[i]]=1;
sort(a+1,a+1+m,cmp);
s[top=1]=a[1];
for(int i=2;i<=m;i++)
insert(a[i]);
while(top>1)
add_edge(s[top-1],s[top]),top--;
rt=s[1];
dfs3(rt);
dfs4(rt,dis[rt],bel[rt]);
dfs5(rt);
dfs6(rt);
ans[bel[rt]]+=siz[1]-siz[rt];
for(int i=1;i<=m;i++)
cout<<ans[A[i]]<<" ";
cout<<endl;
dfs7(rt);
for(int i=1;i<=m;i++)
bo[a[i]]=ans[a[i]]=0;
}
}
```
### 没了