柒葉灬 的博客

柒葉灬 的博客

虚树浅学(偷学日记)

posted on 2019-01-30 15:46:39 | under 算法学习 |

虚树偷(乱)学


概念:虚树就是重新造一棵不存在的树,

相当于把原来树中有用的信息进行压缩,

适用于那种多个询问,每次标记个别点的题目(或许)。

例题:SDOI2011 消耗战 P2495


直接说如何造出虚树:

  1. 把所有点按照dfn排序
  2. 塞入一个点(按照需要塞,例如塞 $1$ )
  3. 找到之前按dfn排序后的的队列的第一个元素 $x$
  4. 求出 $x$ 与栈顶 $stk[top]$ 的 $lca$
  5. 如果 $lca$ 不是 $stk[top]$ , $\dots \dots$ ,详细见代码。
  6. 将 $x$ 塞入栈,
  7. 若队列非空,回到步骤 $3$ 。
  8. 把栈弹空。

代码中有详细注释。

模板:

void add(int a,int b){//链压缩成边,(看情况取最大/小值)
    if(dep[a]<dep[b])swap(a,b);
    int tmp=a,dis=2e9;
    for(int i=17;i>=0;i--){
        if(dep[fa[a][i]]>=dep[b])
            dis=min(dis,mn[a][i]),a=fa[a][i];
    }
    add_edge(b,tmp,dis);
}
bool cmp(int a,int b){
    return dfn[a]<dfn[b];
}
void build(){
    scanf("%d",&K);
    for(int i=1;i<=K;i++)
        scanf("%d",&num[i]);
    sort(num+1,num+1+K,cmp);

    stk[top=1]=1;
    for(int i=1;i<=K;i++){
        int lca=LCA(num[i],stk[top]);
        if(lca!=stk[top]){
        //核心部分
            while(true){
                if(dep[stk[top-1]]<=dep[lca]){
                    add(lca,stk[top]);
                    top--;
                    if(stk[top]!=lca)stk[++top]=lca;
                    break;
                }
                add(stk[top-1],stk[top]);
                top--;
            }
        }
        stk[++top]=num[i];
    }
    while(--top)add(stk[top],stk[top+1]);
}

虚树构造的复杂度,因为虚树构造的时候,

每添加一个点最多增加 $2$ 个点。

所以树的大小最多是 $2*k$ 个