BZOJ 4668 冷战

题目大意

给你一个双向无边图，每次加入一条边或者询问：将两个点联通的最早的边是哪条？

因为是双向的所以没必要真的加边——如果两个点已经联通再连边是没有意义的。维护节点关系那么当然是用并查集啊qwq

插入的时候遵循按秩合并——深度小的合并到深度大的，更新被合并点的答案。

查询的时候首先判断这俩点father一不一样。如果一样的话重新开始，两个点类似LCA向上爬升。每个点的权值是它最后合并的时间戳，所以找到沿途最大的时间戳就是最终的答案了。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,mode,u,v,ans,fa[500010],d[500010],tot;
int main()
{
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d%d",&mode,&u,&v);
		u^=ans,v^=ans;
		switch(mode)
		{
			case 0:
			{
				int tu=0,tv=0;++tot;
				while(fa[u]) u=fa[u],tu++;
				while(fa[v]) v=fa[v],tv++;
				if(u!=v)
				{
					if(tu>tv) swap(u,v);
					fa[u]=v,d[u]=tot;
				}
				break;
			}
			case 1:
			{
				int tu=u,tv=v,du=0,dv=0;ans=0;
				while(fa[u]) u=fa[u],du++;
				while(fa[v]) v=fa[v],dv++;
				if(u==v)
				{
					if(du<dv) swap(du,dv),swap(tu,tv);
					u=tu,v=tv;
					for(int j=1;j<=du-dv;j++) ans=max(ans,d[u]),u=fa[u];
					while(u!=v) ans=max(ans,max(d[u],d[v])),u=fa[u],v=fa[v];
				}
				printf("%d\n",ans);
				break;
			}
		}
	}
	return 0;
}