\(\\\)
\(Description\)
有\(N\)個點，開始沒有邊相連，進行按順序給出的\(M\)個操作：
- \(0\ u\ v\) 將\(u,v\)兩點連一條邊
- \(1\ u\ v\) 查詢\(u,v\)兩點最早在第幾條邊連接的時候被連通
每次詢問輸出一個邊的編號，強制在線。
- \(N,M\in [1,5\times 10^5]\)
\(\\\)
\(Solution\)
在線并查集樹上查詢\(Lca\)。
維護連通性的時候并查集不進行路徑壓縮，只進行按秩合并。考慮到并查集是樹形結構，定義連通塊的秩為塊內樹高\((\)其實定義為塊的大小表現也不錯\()\)。這樣我們得到的是一棵真正的通過并集來連接的并查集樹。
這棵樹上有什么好的性質？答案是兩點到\(Lca\)的路徑上的邊集，是真正將這兩點連接起來的邊集。也就是說，對于兩點查詢的答案，一定是兩點到\(Lca\)路徑上的最大邊編號。
考慮如何求\(Lca\)。因為是在線，所以顯然不能建立倍增數組等基于固定的樹形態的做法。考慮暴力標記，先將兩點跳到同一高度，再共同跳到\(Lca\)處既可，這樣也能很方便的處理路徑\(max\)的問題。
關于復雜度，其實它是合法的。根據按秩合并的原理，在查詢連通塊代表元素時復雜度是\(log\)級別的，同理都是跳父節點的過程，所以查詢\(Lca\)復雜度也是\(log\)級別的。
\(\\\)
\(Code\)
并查集需要維護：當前節點深度，當前節點父節點編號，到父節點的邊權，以及以當前節點為根子樹大小。
注意當前節點深度這個部分，在查詢\(Lca\)之前我們需要先更新一遍以確保深度是正確的，這個過程可以在查詢代表元素的時候同時進行。
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 500010
#define R register
#define gc getchar
using namespace std;int n,m,ans,cnt;struct UFS{int f[N],g[N],d[N],sz[N];UFS(){for(R int i=1;i<N;++i)f[i]=i,d[i]=sz[i]=1;}int find(int x){if(x==f[x])return x;int ans=find(f[x]); d[x]=d[f[x]]+1; return ans;}inline void merge(int x,int y){int fx=find(x),fy=find(y);if(sz[fx]>sz[fy]) fx^=fy^=fx^=fy;sz[fy]+=sz[fx]; f[fx]=fy; g[fx]=cnt; d[fx]=d[fy]+1;}inline int lca(int x,int y){int ans=0;if(d[x]>d[y]) x^=y^=x^=y;while(d[y]>d[x]) ans=max(ans,g[y]),y=f[y];if(x==y) return ans;while(x!=y){ans=max(ans,max(g[x],g[y]));x=f[x]; y=f[y];}return ans;}}ufs;inline int rd(){int x=0; bool f=0; char c=gc();while(!isdigit(c)){if(c=='-')f=1;c=gc();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}return f?-x:x;
}int main(){n=rd(); m=rd();for(R int i=1,op,x,y;i<=m;++i){op=rd(); x=rd()^ans; y=rd()^ans;if(op==0){++cnt;if(ufs.find(x)!=ufs.find(y)) ufs.merge(x,y);}else if(ufs.find(x)!=ufs.find(y)){ans=0;puts("0");}else printf("%d\n",(ans=ufs.lca(x,y)));}return 0;
}
