本文移植自个人的原博客（原文）

概念

虚树可以用来解决在树上的多次询问，约束总询问点数的动态规划问题，相较直接BFS的高复杂度，虚树可以将开销降到与单次询问点数相关的时间复杂度之内。

建树

考虑动态规划合并多个询问节点，只有在遍历到关键的$LCA$时才会计算贡献，且可以直接以$LCA$代替以下节点，所以可以设计出以下算法流程：

  1. 维护一个以$dfn$序为关键字的单调栈，栈顶元素$p$为所有已经处理过的节点中$dfn$最大的节点，一般以根为初始节点，将所有询问节点按$dfn$排序进行插入。

  2. 根据以上算法，一定有$dfn_x>dfn_p$。设栈顶第二个元素为$q$，根据$LCA$与$q$的关系进行分类讨论：

    • 当$LCA=p$时，将$x$入栈。

    • 否则$p$与$q$分别在$lca$的两个子树中，则需要重复以下操作，直到$p$到$lca$中所有节点处理完毕，然后再将$x$入栈。

      • 当$dfn_q > dfn_{lca}$时，连边$(q,p)$,并将$p$退栈。
      • 当$dfn_q = dfn_{lca}$时，连边$(lca,p)$。此时$p$到$lca$已经处理完毕，即可跳出循环。
      • 当$dfn_q < dfn_{lca}$时，此时$lca$在$q−>p$上，建边$(lca,p)$，以$lca$代替$p$在栈中的位置。此时$p$到$lca$已经处理完毕，即可跳出循环。

相关题目

SDOI2011 消耗战

题目链接

Luogu 2495

题目描述

题目描述

题解

设$f_x$为覆盖以$x$为跟子树的最小代价，则有$f_x=min(\sum f_{sonx},g_x)$，其中$g_x$代表根到$x$路径上的最小权值边，用虚树优化即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+1;
const ll inf = 1e15;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int n,m,k,head[N],d[N],cnt,f[N][19],q[N],dfn[N],totw,st[N],vis[N];
ll dp[N],g[N];
struct nd{
    int ne,to;ll w;
}e[N*2];

void in(int x,int y,ll w){
    if(x==y)return;
    e[++cnt].to=y;e[cnt].ne=head[x];head[x]=cnt;e[cnt].w=w;
}

void dfs(int x,int fa=-1){
    dfn[x]=++totw;
    for(int i=head[x];i;i=e[i].ne)
    if(e[i].to!=fa){
        int y=e[i].to;
        f[y][0]=x;
        g[y]=min(g[x],e[i].w);
        d[y]=d[x]+1;
        dfs(y,x);
    }
}

int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);
    for(int i=18;i>=0;--i)
    if(d[f[x][i]]>=d[y])x=f[x][i];
    if(x==y)return x;
    for(int i=18;i>=0;--i)
    if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}

bool cmp(int a,int b){
    return dfn[a]<dfn[b];
}
int T=0;
ll get(int x){
    ll k=0;
    for(int i=head[x];i;i=e[i].ne)k+=get(e[i].to);
    head[x]=0;
    return dp[x]=(vis[x]!=T?min(g[x],k):g[x]);
}

ll solve(){
    cnt=0;++T;
    sort(q+1,q+k+1,cmp);
    for(int i=1;i<=k;++i)vis[q[i]]=T;
    int L=0;
    st[++L]=1;
    for(int i=1;i<=k;++i){
        int x=q[i],l=lca(x,st[L]);
        if(l==st[L])st[++L]=x;
        else{
            while(1){
                if(dfn[l]>=dfn[st[L-1]]){
                    in(l,st[L--],0);
                    if(st[L]!=l)st[++L]=l;
                    break;
                }
                in(st[L-1],st[L],0),L--;
            }
            if(x!=st[L])st[++L]=x;
        }
    }
    while(--L)in(st[L],st[L+1],0);
    return get(1);
}


int main(){
//  freopen("c.in","r",stdin);
    n=read();
    for(int i=1,x,y,w;i<n;++i){
        x=read(),y=read(),w=read();
        in(x,y,w);in(y,x,w);
    }
    d[1]=1;g[1]=inf;dfs(1);
    for(int j=1;j<19;++j)
    for(int i=1;i<=n;++i)
    f[i][j]=f[f[i][j-1]][j-1];
    m=read();
    memset(head,0,sizeof(head));cnt=0;
    while(m--){
        k=read();
        for(int j=1;j<=k;++j)q[j]=read();
        printf("%lld\n",solve());
    }
}

HNOI2014 世界树

题目链接

Luogu 3233

题目描述

题目描述

题解

先建立虚树，两遍DP找出每个点的控制点，然后在考虑虚树上每一条边的贡献，如果两个顶点属于同一个控制点，直接计算即可，否则二分出控制点不同的位置在计算贡献，注意这一步不应计算端点，否则会导致重复计算，对于没有考虑到的点，其控制点一定在第一个在虚树上的父亲节点上，也要计算在内，最后应注意清空数组。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+1;

int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}

int n,k,q[N],bel[N],a[N],c[N],d[N],dfn[N],f[N][19],ans[N],g1[N],head[N],cnt,st[N],sz[N];
struct nd{
    int ne,to;
}e[N*2];

void in(int x,int y){
    if(x==y||!x||!y)return;
    e[++cnt].to=y;e[cnt].ne=head[x];head[x]=cnt;
}

int dfs(int x,int fa=-1){
    static int totw=0;
    dfn[x]=++totw;sz[x]=1;
    for(int i=head[x];i;i=e[i].ne)
    if(e[i].to!=fa){
        int y=e[i].to;
        d[y]=d[x]+1;f[y][0]=x;
        dfs(y,x);
        sz[x]+=sz[y];
    }
}

int lca(int x,int y){
//    cout<<x<<" "<<y<<" ";
    if(d[x]<d[y])swap(x,y);
    for(int i=18;i>=0;--i)
    if(d[f[x][i]]>=d[y])x=f[x][i];
    if(x==y){
//        cout<<x<<endl;
        return x;
    }
    for(int i=18;i>=0;--i)
    if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
//    cout<<f[x][0]<<endl;
    return f[x][0];
}

int dis(int x,int y){
    return d[x]+d[y]-2*d[lca(x,y)];
}

bool cmp(int a,int b){
    return dfn[a]<dfn[b];
}

void dfs1(int x,int fa=-1){
//    cout<<x<<" ";
    c[++c[0]]=x;g1[x]=sz[x];
    for(int i=head[x];i;i=e[i].ne)
    if(e[i].to!=fa){
        int y=e[i].to;
        dfs1(y,x);
        if(!bel[y])continue;
        if(!bel[x])bel[x]=bel[y];
        else{
            int d1=dis(bel[x],x);
            int d2=dis(bel[y],x);
            if(d2<d1||(d2==d1&&bel[y]<bel[x]))bel[x]=bel[y];
        }
    }
}

void dfs2(int x,int fa=-1){
    for(int i=head[x];i;i=e[i].ne)
    if(e[i].to!=fa){
        int y=e[i].to;
        if(!bel[y])bel[y]=bel[x];
        else{
            int d1=dis(bel[x],y);
            int d2=dis(bel[y],y);
            if(d1<d2||(d1==d2&&bel[x]<bel[y]))bel[y]=bel[x];
        }
        dfs2(y,x);
    }
}

void solve(int x,int y){
//    cout<<x<<" "<<y<<endl;
    int son=y,mid=y,now,d1,d2;
    for(int i=18;i>=0;--i)
    if(d[f[son][i]]>d[x])son=f[son][i];
    g1[x]-=sz[son];
    if(bel[x]==bel[y])return void(ans[bel[x]]+=sz[son]-sz[y]);
    for(int i=18;i>=0;--i){
        now=f[mid][i];
        if(d[now]<=d[x])continue;
        d1=dis(bel[x],now);d2=dis(bel[y],now);
        if(d2<d1||(d2==d1&&bel[y]<bel[x]))mid=now;
    }
    ans[bel[x]]+=sz[son]-sz[mid];
    ans[bel[y]]+=sz[mid]-sz[y];
    return;
}

void solve(){
    sort(q+1,q+k+1,cmp);cnt=0;c[0]=0;
    for(int i=1;i<=k;++i)bel[q[i]]=q[i];
    int L=0;
    st[++L]=1;
    for(int i=1;i<=k;++i){
        int x=q[i],l=lca(x,st[L]);
        while(1){
            if(dfn[l]>=dfn[st[L-1]]){
                in(l,st[L--]);
                if(st[L]!=l)st[++L]=l;
                break;
            }
            in(st[L-1],st[L]);L--;
        }
        if(x!=st[L])st[++L]=x;
    }
    while(--L)in(st[L],st[L+1]);

    dfs1(1);dfs2(1);
//    for(int i=1;i<=c[0];++i)cout<<bel[c[i]]<<" ";cout<<endl;
    for(int i=1;i<=c[0];++i){
        int x=c[i];
        for(int j=head[x];j;j=e[j].ne)
        solve(x,e[j].to);
    }
    for(int i=1;i<=c[0];++i)ans[bel[c[i]]]+=g1[c[i]];
    for(int i=1;i<=k;++i)printf("%d ",ans[a[i]]);printf("\n");
    for(int i=1;i<=c[0];++i){
        int x=c[i];
        head[x]=ans[x]=g1[x]=bel[x]=0;
    }
    return;
}

int main(){
//    freopen("c.in","r",stdin);
    n=read();
    for(int i=1,x,y;i<n;++i)
    x=read(),y=read(),in(x,y),in(y,x);
    int Q=read();
    d[1]=1;dfs(1);
    for(int j=1;j<19;++j)
    for(int i=1;i<=n;++i)
    f[i][j]=f[f[i][j-1]][j-1];
    memset(head,0,sizeof(head));cnt=0;
    while(Q--){
        k=read();
        for(int i=1;i<=k;++i)a[i]=q[i]=read();
        solve();
    }
}

HEOI2014 大工程

题目链接

Luogu 4103

题目描述

题目描述1

题目描述2

题解

虚树裸题。但代码量不小，需要处理的东西不少。

逻辑清晰的实现会让代码难度降低一个等级。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+1;
const int inf = 1e8;


int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}

int n,m,f[N][21],st[N],dfn[N],q[N],head[N],d[N],cnt,k,vis[N],T,sz[N];
struct nd{
    int ne,to;
}e[N*2];

void in(int x,int y){
    if(x==y||!x||!y)return;
    e[++cnt].to=y;e[cnt].ne=head[x];head[x]=cnt;
}

int dfs(int x,int fa=-1){
    static int totw=0;
    dfn[x]=++totw;
    for(int i=head[x];i;i=e[i].ne)
    if(e[i].to!=fa){
        int y=e[i].to;
        f[y][0]=x;
        d[y]=d[x]+1;
        dfs(y,x);
    }
}

bool cmp(int a,int b){
    return dfn[a]<dfn[b];
}

int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);
    for(int i=20;i>=0;--i)
    if(d[f[x][i]]>=d[y])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];
}


ll s[N];
ll ans=0;
int mx=0,mn=inf,mnn[N],mxx[N];

void get(int x){
    s[x]=0;
    sz[x]=(vis[x]==T);
    mnn[x]=(vis[x]==T?0:inf);
    mxx[x]=(vis[x]==T?0:-inf);
    for(int i=head[x];i;i=e[i].ne){
        int y=e[i].to;
        get(y);
        ans+=(s[x]+sz[x]*(d[y]-d[x]))*sz[y]+s[y]*sz[x];
        sz[x]+=sz[y];
        s[x]+=s[y]+(d[y]-d[x])*sz[y];
        mx=max(mx,mxx[x]+mxx[y]+d[y]-d[x]);
        mn=min(mn,mnn[x]+mnn[y]+d[y]-d[x]);
        mxx[x]=max(mxx[x],mxx[y]+d[y]-d[x]);
        mnn[x]=min(mnn[x],mnn[y]+d[y]-d[x]);
    }
    head[x]=0;
}

void solve(){
    sort(q+1,q+k+1,cmp);cnt=0;++T;
    for(int i=1;i<=k;++i)vis[q[i]]=T;
    ans=0;mx=0;mn=inf;
    int L=0;
    st[++L]=1;
    for(int i=1;i<=k;++i){
        int x=q[i],l=lca(x,st[L]);
        while(1){
            if(d[l]>=d[st[L-1]]){
                in(l,st[L--]);
                if(l!=st[L])st[++L]=l;
                break;
            }
            in(st[L-1],st[L]);L--;
        }
        if(x!=st[L])st[++L]=x;
    }
    while(--L)in(st[L],st[L+1]);
    get(1);
    printf("%lld %d %d\n",ans,mn,mx);
}

int main(){
//    freopen("c.in","r",stdin);
    n=read();
    for(int i=1,x,y;i<n;++i)
    x=read(),y=read(),in(x,y),in(y,x);
    d[1]=1;dfn[0]=inf;dfs(1);
    for(int j=1;j<21;++j)
    for(int i=1;i<=n;++i)
    f[i][j]=f[f[i][j-1]][j-1];
    memset(head,0,sizeof(head));
    int Q=read();
    while(Q--){
        k=read();
        for(int i=1;i<=k;++i)q[i]=read();
        solve();
    }
}