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=1000010,R=50000000; char buf[R+4],*ptr=buf-1; inline int _int(){ int x=0,c=*++ptr; while(c<48)c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x; } int stk[16],stp=0; inline void int_(int x){ if(!x)stk[++stp]=0; while(x)stk[++stp]=x%10,x/=10; while(stp)putchar(stk[stp--]+48); putchar(10); } int n,m; bool ed[N]; int f[N],q[N],ql,qr,dep[N],fa[N],id[N],aid[N]; int et[N*2],enx[N*2],e0[N],eid[N*2],ep=2; int qs[N*2],qw[N*2],qp=0,as[N],ap=0; 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,1,R,stdin); n=_int();m=_int(); for(int i=1;i<=n;i++)f[i]=i; for(int i=1;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=0; q[qr++]=1; dep[1]=1; while(ql!=qr){ int w=q[ql++]; for(int i=e0[w];i;i=enx[i])if(int u=et[i]){ et[i^1]=0; fa[u]=w; id[u]=eid[i]; dep[q[qr++]=u]=dep[w]+1; } } for(int i=0;i<m;i++)if(_int()==1){ qs[qp]=1;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]=1; a=f[a]=get(fa[a]); } } for(int i=1;i<=n;i++)f[i]=i; ql=qr=0; q[qr++]=1; 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]=1,f[get(u)]=get(w); q[qr++]=u; } } for(int i=qp-1;~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 0; }