冷战

题意

给定n个点以及两种操作：

1. 将两个点连接在一起

2. 询问两个点最早在什么时候联通。

强制在线。

---

思路

将时间作为权值，在并查集上跑lca即可。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

	template<typename T>inline void read (T &x) {
		x=0;T f=1;char c=getchar();
		for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
		for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
		x*=f;
	}

	template<typename T>inline void write (T x) {
		if (x<0) putchar('-'),x*=-1;
		if (x>=10) write(x/10);
		putchar(x%10+'0');
	}

}

using namespace StandardIO;

namespace Project {
	
	const int N=500500;
	
	int n,m;
	int fa[N],dep[N],size[N],t[N],last,tim;
	
	int find (int x) {
		return (x==fa[x])?x:find(fa[x]);
	}
	int get_dep (int x) {
		return (x==fa[x])?0:get_dep(fa[x])+1;
	}
	inline void merge (int x,int y,int val) {
		if (x==y) return;
		if (size[x]<size[y]) swap(x,y);
		fa[y]=x,t[y]=val;
		if (size[x]==size[y]) ++size[x];
	}
	inline int lca (int x,int y) {
		if (find(x)!=find(y)) return 0;
		int depx=get_dep(x),depy=get_dep(y),res=0;
		if (depx<depy) swap(x,y),swap(depx,depy);
		while (depx!=depy) {
			res=max(res,t[x]),x=fa[x],--depx;
		}
		while (x!=y) {
			res=max(res,max(t[x],t[y])),x=fa[x],y=fa[y];
		}
		return res;
	}
	

	inline void MAIN () {
		read(n),read(m);
		for (register int i=1; i<=n; ++i) fa[i]=i;
		while (m--) {
			int op,x,y;
			read(op),read(x),read(y),x^=last,y^=last;
			if (op==0) {
				x=find(x),y=find(y);
				merge(x,y,++tim);
			} else {
				write(last=lca(x,y)),putchar('
');
			}
		}
	}
	
}

int main () {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	Project::MAIN();
}