2018-team4-modules-虚树

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
int sta[maxn],a[maxn];
inline bool cmp(const int &i,const int &j){
    return dfn[i] < dfn[j];
}
int main(){
    int n;read(n);
    for(int i=1,u,v;i<n;++i){
        read(u);read(v);
        pic1.add(u,v);//pic1代表原树，表示在原树中加边
        pic1.add(v,u);
    }
    pic1.dfs(1);pic1.dfs(1,1);
    pic2.cnt = 0;
    read(num);
    for(int i=1;i<=num;++i){
        read(a[i]);
        col[a[i]] = true;
    }
    sort(a+1,a+num+1,cmp);
    int top = 0;
    //以下的所有pic2.add均表示所建虚树的边
    for(int i=1;i<=num;++i){
        if(top == 0) sta[++top] = a[i];
        else{
            int lc = lca(sta[top],a[i]);
            while(dfn[sta[top]] > dfn[lc]){
                if(dfn[sta[top-1]] <= dfn[lc]){
                    pic2.add(lc,sta[top]);
                    if(sta[--top] != lc)sta[++top] = lc;
                    break;
                }
                pic2.add(sta[top-1],sta[top]);
                -- top;
            }
            sta[++top] = a[i];
        }
    }
    while(top > 1) pic2.add(sta[top-1],sta[top]),top--;
    return 0;
}
}}}

int sta[maxn],a[maxn];
inline bool cmp(const int &i,const int &j){
    return dfn[i] < dfn[j];
}
int main(){
    int n;read(n);
    for(int i=1,u,v;i<n;++i){
        read(u);read(v);
        pic1.add(u,v);//pic1代表原树，表示在原树中加边
        pic1.add(v,u);
    }
    pic1.dfs(1);pic1.dfs(1,1);
    pic2.cnt = 0;
    read(num);
    for(int i=1;i<=num;++i){
        read(a[i]);
        col[a[i]] = true;
    }
    sort(a+1,a+num+1,cmp);
    int top = 0;
    //以下的所有pic2.add均表示所建虚树的边
    for(int i=1;i<=num;++i){
        if(top == 0) sta[++top] = a[i];
        else{
            int lc = lca(sta[top],a[i]);
            while(dfn[sta[top]] > dfn[lc]){
                if(dfn[sta[top-1]] <= dfn[lc]){
                    pic2.add(lc,sta[top]);
                    if(sta[--top] != lc)sta[++top] = lc;
                    break;
                }
                pic2.add(sta[top-1],sta[top]);
                -- top;
            }
            sta[++top] = a[i];
        }
    }
    while(top > 1) pic2.add(sta[top-1],sta[top]),top--;
    return 0;
}