bzoj3319: 黑白树

Description

给定一棵树，边的颜色为黑或白，初始时全部为白色。维护两个操作：
1.查询u到根路径上的第一条黑色边的标号。
2.将u到v    路径上的所有边的颜色设为黑色。
Notice:这棵树的根节点为1

Input

第一行两个数n,m分别表示点数和操作数。
接下来n-?    1行，每行2个数u,v.表示一条u到v的边。
接下来m行，每行为以下格式：
1 v 表示第一个操作
2 v u 表示第二种操作

Output

对于每个询问，输出相应答案。如果不存在，输出0。

由于边只会由白变黑，所以总的边修改次数为O(n)，用并查集维护每个点到根的路径上最深的白边位置，预处理出边的染色顺序

逆序处理操作，用并查集维护，一开始把所有点合并到到根路径上第一条黑边，每取消一次染色就把边的下侧节点合并到上侧

#include<cstdio>

const int N=,R=;

char buf[R+],*ptr=buf-;

inline int _int(){

    int x=,c=*++ptr;

    while(c<)c=*++ptr;

    while(c>)x=x*+c-,c=*++ptr;

    return x;

}

int stk[],stp=;

inline void int_(int x){

    if(!x)stk[++stp]=;

    while(x)stk[++stp]=x%,x/=;

    while(stp)putchar(stk[stp--]+);

    putchar();

}

int n,m;

bool ed[N];

int f[N],q[N],ql,qr,dep[N],fa[N],id[N],aid[N];

int et[N*],enx[N*],e0[N],eid[N*],ep=;

int qs[N*],qw[N*],qp=,as[N],ap=;

inline int get(int x){

    int a=x,c;

    while(x!=f[x])x=f[x];

    while(x!=(c=f[a]))f[a]=x,a=c;

    return x;

}

int main(){

    fread(buf,,R,stdin);

    n=_int();m=_int();

    for(int i=;i<=n;i++)f[i]=i;

    for(int i=;i<n;i++){

        int a=_int(),b=_int();

        et[ep]=b;enx[ep]=e0[a];eid[ep]=i;e0[a]=ep++;

        et[ep]=a;enx[ep]=e0[b];eid[ep]=i;e0[b]=ep++;

    }

    ql=qr=;

    q[qr++]=;

    dep[]=;

    while(ql!=qr){

        int w=q[ql++];

        for(int i=e0[w];i;i=enx[i])if(int u=et[i]){

            et[i^]=;

            fa[u]=w;

            id[u]=eid[i];

            dep[q[qr++]=u]=dep[w]+;

        }

    }

    for(int i=;i<m;i++)if(_int()==){

        qs[qp]=;qw[qp++]=_int();

    }else{

        int a=get(_int()),b=get(_int());

        while(a!=b){

            if(dep[a]<dep[b]){int t=a;a=b;b=t;}

            qw[qp++]=a;

            aid[a]=id[a];

            ed[a]=;

            a=f[a]=get(fa[a]);

        }

    }

    for(int i=;i<=n;i++)f[i]=i;

    ql=qr=;

    q[qr++]=;

    while(ql!=qr){

        int w=q[ql++];

        for(int i=e0[w];i;i=enx[i])if(int u=et[i]){

            if(ed[w]&&!ed[u])ed[u]=,f[get(u)]=get(w);

            q[qr++]=u;

        }

    }

    for(int i=qp-;~i;i--)

        if(qs[i])as[ap++]=aid[get(qw[i])];

        else f[get(qw[i])]=get(fa[qw[i]]);

    while(ap)int_(as[--ap]);

    return ;

}