虚树

-1 鲜花

久仰大名，先前在相当多的模拟赛或者正式比赛的题目中都见到了，但是一直没有认真学过，现在又来严肃填坑。

0 前置芝士

• 单调栈
• 复杂度优秀的在线LCA（如倍增/树剖/四毛子）
• 树形dp

1 前言

虚树这个东西非常好理解而且好用，其核心思想在于 ”随用随取“。因为往往在一个树形结构中，并非所有的点都是我们需要处理的，甚至有大量冗余信息，如果能建出一颗树只保留原本这棵树的大致结构和我们需要的信息，往往可以显著降低复杂度，从而让看起来不对的暴力拿很多分甚至通过。

2 原理

一道例题：【模板】虚树 / [SDOI2011] 消耗战。

不考虑数据范围，DP显然是好想的。令 $f_u$ 表示 $u$ 子树中所有关键点全部被断开的最小代价，显然可以枚举 $u$ 的每一个儿子 $v$ 来转移：

• 若 $v$ 为关键点，则一定要切断当前边，即 $f_u\leftarrow dis(u,v)$
• 若 $v$ 不是关键点，则显然可以选择切断当前边或者选择切断 $v$ 子树内一些边的方案，即 $f_u\leftarrow \min(dis(u,v),f_v)$

但是发现直接这么做肯定是会爆掉的，但是关键点的数量很少。我们发现在整个转移过程中有用的点事实上只有三种：

• 关键点
• 根节点
• 任意两个关键点的 LCA

所以考虑建一颗虚树只保留这些东西。

建立虚树的方式有两种，下面介绍一种我个人很喜欢的单调栈建法。

单调栈建虚树的本质是将目前的虚树分为了两部分：已经建好的和“最右链”，并且用单调栈维护这一条“最右链”，因为一条链的 $dfn$ 序一定是自下而上递减的。所谓“最右链”就是你这一条链上还能够继续添加东西的一条链，我们钦定在其左边的部分都是已经完成的，在其右边的部分都是还没建的。

先算出整棵树的 $dfn$ 序，将关键点按照 $dfn$ 序从小到大排序后进行如下操作。

1. 初始化，清空虚树和关键点标记，将根节点入栈。

2. 加入一个点，分类讨论属于以下哪种情况：

   • 属于当前最右链上的一点。这种情况直接入栈即可

   • 不属于当前最右链上。这种情况我们应该更新最右链，也就是把已经不属于最右链的点出栈并加到虚树中。我们令 $st_{top}$ 和 $st_{top-1}$ 分别表示栈顶和栈的次顶端，$lc$ 表示新加入的点和 $st_{top}$ 的LCA。

     • 若 $lc$ 为 $st_{top}$ 和 $st_{top-1}$ 之间的一个点，则显然需要把边 $(lc,st_{top})$ 加入虚树。然后弹出栈顶并且加入 $lc$。
     • 若 $lc$ 为 $st_{top-1}$，则跟上面相同，只是不需要再重复加入 $lc$ 了。
     • 若 $lc$ 为 $st_{top-1}$ 更上面的点，则显然 $lc$ 下方的链都不属于最右链了，应该将其全部弹出并且都加入虚树。然后再分为上面的情况进行讨论。

   • 需要注意的是，上述过程完成后都需要将要加入到点加入栈中。同时，所有虚树的边权都应为原图对应路径上的最小边权，因为切断关键点时可以选择代价最小的切断。

3. 最后把剩余栈中的链也加入虚树，到这里虚树就建好了。

然后在新建的虚树上跑DP就可以了。DP的逻辑和原本的完全一致。

然后你就学会虚树了/bx/bx/bx。

3 实现

虚树建立完成后还需要注意的问题就是清空，可以考虑跑完DP再随便写一个清空的dfs就可以了。

丑陋的部分代码如下：

struct edge{
    int to,val;
};
std::vector<edge> g[N],vt[N];
int n,q,n1,dfn[N],dep[N],fa[N][30],val[N][30],f[N];
bool isg[N];
int st[N],top;
int tot;
std::vector<int> node;
void dfs(int u,int father){
    dep[u]=dep[father]+1;
    dfn[u]=++tot;
    fa[u][0]=father;
    for(auto &i:g[u]){
        if(i.to==father)continue;
        val[i.to][0]=i.val;
        dfs(i.to,u);
    }   
}
void init_lca(){
    for(int j=1;j<=25;++j){
        for(int i=1;i<=n;++i){
            fa[i][j]=fa[fa[i][j-1]][j-1];
            val[i][j]=std::min(val[i][j-1],val[fa[i][j-1]][j-1]);
        }
    }
}
int lca(int u,int v){
    if(dep[u]<dep[v])std::swap(u,v);
    for(int i=25;i>=0;--i){
        if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
    }
    if(u==v)return u;
    for(int i=25;i>=0;--i){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}

int dist(int u,int v){
    int res=inf;
    if(dep[u]<dep[v])std::swap(u,v);
    for(int i=25;i>=0;--i){
        if(dep[fa[u][i]]>=dep[v]){res=std::min(res,val[u][i]);u=fa[u][i];}
    }
    if(u==v)return res;
    for(int i=25;i>=0;--i){
        if(fa[u][i]!=fa[v][i]){
            res=std::min(res,val[u][i]),u=fa[u][i];
            res=std::min(res,val[v][i]),v=fa[v][i];
        }
    }
    return std::min(res,std::min(val[u][0],val[v][0]));
}
bool cmp(int x,int y){
    return dfn[x]<dfn[y];
}
void vt_addedge(int u,int v,int w){
    vt[u].push_back({v,w});
    vt[v].push_back({u,w});
}
void buildvt(){
    std::sort(node.begin(),node.end(),cmp);
    st[top=1]=1;
    for(auto &i:node){
        isg[i]=1;
        if(i==1)continue;
        int lc=lca(i,st[top]);
        if(lc==st[top]){goto end;}
        while(top>=2&&dfn[lc]<dfn[st[top-1]]){
            vt_addedge(st[top-1],st[top],dist(st[top-1],st[top]));
            top--;
        }
        vt_addedge(lc,st[top],dist(lc,st[top]));
        if(dfn[lc]>dfn[st[top-1]])st[top]=lc;
        else top--;
        end:
        st[++top]=i;
    } 
    for(int i=1;i<top;++i){
        vt_addedge(st[i],st[i+1],dist(st[i],st[i+1]));
    }
}
void solve(int u,int father){
    for(auto &i:vt[u]){
        if(i.to==father)continue;
        solve(i.to,u);
        if(isg[i.to])f[u]+=(i.val);
        else f[u]+=std::min(f[i.to],i.val);
    }
}
void clr(int u,int father){
    for(auto &i:vt[u]){
        if(i.to==father)continue;
        clr(i.to,u);
    }
    vt[u].clear();isg[u]=0;f[u]=0;
}
signed main(){
    n=read();
    for(int i=1;i<n;++i){
        int u=read(),v=read(),w=read();
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    val[1][0]=inf;
    dfs(1,0);
    init_lca();
    q=read();
    while(q--){
        n1=read();
        node.clear();
        for(int i=1;i<=n1;++i){
            int u=read();
            node.push_back(u);
        }
        buildvt()
        solve(1,0);
        printf("%lld\n",f[1]);
        clr(1,0);
    }
}

4 时间复杂度分析

建立虚树的复杂度为 $O(k\log k)$，瓶颈在于对关键点排序和每加入一个点求 $LCA$，当然如果用四毛子可以规避掉后者。

每次建立的虚树至多有不超过 $2k$ 个顶点。因为有 $k$ 个关键点，相邻两个点的LCA共 $k-1$ 个点，以及如果没有给补上的根节点。

虚树大小确定了，树上DP的过程显然是 $O(k)$ 的。因此总复杂度 $O(k\log k)$。

5 例题

[HEOI2014] 大工程

我的题解：P4103 题解。