「题解」冷战 coldwar(未完待续)

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;
using std::swap;
const int MAXN=500000+5;
const int MAXM=500000+5;
int n,m;
int opt,u,v;
int lastans,cnt;
int ID[MAXN],fa[MAXN],rank[MAXN],dis[MAXN];
int path[2][MAXN];
int find(int);
void merge(int,int,int);
int Query(int,int);
int main(void){
    freopen("coldwar.in","r",stdin);
    freopen("coldwar.out","w",stdout);
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&opt,&u,&v);
        u^=lastans;v^=lastans;//强制在线
        //printf("u=%d v=%d\n",u,v);
        if(opt==0)
            merge(u,v,++cnt);
        if(opt==1)
            printf("%d\n",lastans=Query(u,v));
    }
    return 0;
}
void merge(int a,int b,int len){
    a=find(a),b=find(b);
    if(a==b)
        return;
    if(rank[a]>rank[b])
        swap(a,b);
    ID[a]=b;
    fa[a]=b;
    dis[a]=len;
    rank[b]=max(rank[b],rank[a]+1);
    return;
}
int find(int x){
    if(!ID[x])
        return rank[x]=1,ID[x]=x;
    else if(ID[x]==x)
        return x;
    else
        return ID[x]=find(ID[x]);
}
int Query(int u,int v){
    if(find(u)!=find(v))
        return 0;
    if(u==v)
        return 0;
    register int cntu=0,cntv=0;
    register bool f1=false,f2=false;
    while(fa[u])
        path[0][cntu++]=u,u=fa[u];
    path[0][cntu]=u;
    while(fa[v])
        path[1][cntv++]=v,v=fa[v];
    path[1][cntv]=v;
    while(path[0][cntu]==path[1][cntv]){
        if(!cntu)
            f1=true;
        if(!cntv)
            f2=true;
        cntu=max(cntu-1,0);
        cntv=max(cntv-1,0);
    }
    if(f1)
        return dis[path[1][cntv]];
    else if(f2)
        return dis[path[0][cntu]];
    else
        return max(dis[path[0][cntu]],dis[path[1][cntv]]);
}