虚树学习笔记

chen_qian · 2021-05-06 13:37:21 · 个人记录

在一些树上问题中，可能会有一些询问，每次询问给出一些关键点，这些关键点的总数是可以接受的，但是我们不能对于每一次询问都进行一次对所有点的遍历，可以发现的是由于总数一定，所以关键点相对于所有点来说都是很稀疏的。我们可不可以重构这颗树，让树上面只剩下关键点呢？虚树就是为了解决这样一类问题而诞生的。

• 虚树：虚树是所有关键点与这些关键点两两之间在原树上的 \text{lca} 所构成的一颗原树的重构树，之所以要有 \text{lca} 是为了记录下原本的树的结构，也即关键点之间的关系。假如关键点有 m 个，那么可以证明这颗虚树上的节点的个数至多有 2m-1 个。

  • 证明：如果我们将所有的点按照 \text{dfs} 序进行排列，那么每加入一个点，其要么在当前最浅的 \text{LCA} 子树内部，要么在外部，后者会产生一个 \text{LCA}。而前者不会产生新的 \text{LCA} 得证。

• 虚树的建立

  • 建立虚树的本质是在用一个栈来维护一条以根为起点的树链。例如下图

  • 有标号的点表示关键点，而绿色边就是我们当前维护的链。如果 2 有一个儿子关键点 4，我们就需要优先将 4 加入栈中。为了保证所有处于同一条树链的关键点一起被加入，我们需要按照 \text{dfs} 序排列。

  • 那么现在要求加入 3 了，那么所有与 3 不在同一根树链上的都必须退出，所以我们求出 3 与当前链底 2 的 \text{LCA}。那么所有的在栈中且 \text{dfs} 序比 \text{LCA} 大的都不是跟 3 同一个链上的，全部退出，并向父亲连边。然后，根据栈顶是不是 \text{LCA} ，决定是否把 \text{LCA} 加入栈。最后把 3 入栈即可。

void build(){
    sort(h+1,h+m+1,cmp);//按照dfs序排序 
    top=0;idx=0;//清空链式前向星 
    stk[++top]=1;//不管 1 是不是关键点，优先加入 1
    for(int i=1;i<=m;i++){
        if(h[i]==1) continue;
        int lca=LCA(stk[top],h[i]);
        if(lca!=stk[top]){
            while(dfn[stk[top-1]]>dfn[lca])  add(stk[top-1],stk[top]),top--;//add 指加边操作 
            if(stk[top-1]!=lca){
                head[lca]=0;//清空前向星 
                add(lca,stk[top]);//lca 处于两者之间，那么下一个点应该是 lca 的儿子 
                stk[top]=lca;
            }
            else{
                add(stk[top-1],stk[top]);//直接加 
                top--;
            }
        }
        head[h[i]]=0;
        stk[++top]=h[i];
    } 
    for(int i=1;i<top;i++) add(stk[top],stk[top+1]);//加上没加的边 
}