并查集+启发式合并+LCA思想 || 冷战 || BZOJ 4668

题面：bzoj炸了，以后再补发

题解：

并查集，然后对于每个点记录它与父亲节点联通的时刻 tim ，答案显然是 u 到 v 的路径上最大的 tim 值。启发式合并，把 size 小的子树往大的上并，可以证明树高是 log N 的（我不会），

所以最后套一个LCA思想，直接向上跳着找出路径上最大的 tim 值即为答案，时间复杂度O(N log N)。

代码：

 #include<cstdio>

 #include<iostream>

 #define max(a,b) ((a)>(b)?(a):(b))

 using namespace std;

 inline int rd(){

     int x=;char c=getchar();

     while(c<''||c>'')c=getchar();

     while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

     return x;

 }

 const int maxn=5e5+,maxm=5e5+;

 int N,M,o,u,v,ans=,fa[maxn],tim[maxn],now=,f1,f2,siz[maxn];

 int now_tim=;

 inline int getf(int n){

     if(fa[n]==n) return n;

     return getf(fa[n]);

 }

 inline int getdep(int n){

     int cnt=;

     while(fa[n]!=n){

         cnt++;

         n=fa[n];

     }

     return cnt;

 }

 int main(){

     N=rd(); M=rd();

     for(int i=;i<=N;i++) fa[i]=i,siz[i]=;

     while(M--){

         o=rd(); u=rd(); v=rd();

         u=u^ans; v=v^ans;

         if(o==){

             now_tim++;

             f1=getf(u); f2=getf(v);

             if(f1!=f2){

                 if(siz[f1]>siz[f2]) swap(f1,f2);

                 siz[f2]+=siz[f1];

                 fa[f1]=f2;

                 tim[f1]=now_tim;

             }

         }

         else{

             f1=getf(u); f2=getf(v);

             ans=;

             if(f1!=f2) {

                 printf("%d\n",ans);

                 continue;

             }

             int dep1=getdep(u),dep2=getdep(v);

             if(dep1<dep2) swap(dep1,dep2),swap(u,v);

             while(dep1>dep2){

                 dep1--;

                 ans=max(ans,tim[u]);

                 u=fa[u];

             }

             if(u!=v){

                 while(fa[u]!=fa[v]){

                     ans=max(ans,tim[u]);

                     ans=max(ans,tim[v]);

                     u=fa[u]; v=fa[v];

                 }

                 ans=max(ans,tim[u]);

                 ans=max(ans,tim[v]);

             }

             printf("%d\n",ans);

         }

     }

     return ;

 }

---

By:AlenaNuna