自动搬运

查看原文

来自洛谷，原作者为

	yurzhang どんな時も——夏の青さを、覚えていた。

搬运于2025-08-24 22:11:17，当前版本为作者最后更新于2019-08-07 07:48:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的阅读体验 -> 推销博客

前言

这个题其实没有多难，静下来慢慢写还是十分可做的，不失为一道 $\text{LCT}$ 练手好题。

正文

首先看到 $1$ 操作连边，第一反应应该就是 $\text{Link/Cut Tree}$ 了，然而怎么维护割边割点数量呢？我们分开讨论。

割边

考虑对于一个环，环上所有边一定不会是割边；而对于一条链，链上所有边一定是割边。

我们可以直接维护每条边是不是割边，初始时所有边都是割边，当某次加边操作产生了环，则环上所有边都不会成为割边了。

具体来讲，边转点后所有边权值均为 $1$ ，当某次 $\text{Link}$ 的两结点已经连通，则将两结点间的链上的边全部赋值为 $0$ ，同时维护和即可。

割点

割点不像割边那样好处理了。

考虑静态的情况，静态割点有一个比较套路的方法是用圆方树，我们可以尝试动态地维护一棵圆方树：每次连边产生环就将环上所有点连到一个方点上来。

考虑这样做的复杂度：

假设环的长度是 $L$ ，每次会用 $O(L\log n)$ 的复杂度删去一个长为 $O(L)$ 的环，均摊复杂度为 $O(n\log n)$ 。

最后

于是使用两棵 $\text{LCT}$ 分别维护割边和割点即可。

参考代码：

#include <cstdio>

#define N 200010
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]

inline void swap(int&a,int&b) {
	int tmp(a); a=b,b=tmp;
}

namespace Summer {
	int ch[N][2],fa[N],rev[N],val[N],sumv[N],mark[N];
	inline void reverse(int x) {
		if(x) {
			swap(lc(x),rc(x));
			rev[x]^=1;
		}
	}
	inline void NaCly_Fish_Orz(int x) {
		if(x) {
			val[x]=sumv[x]=0;
			mark[x]=1;
		}
	}
	inline void up(int x) {
		sumv[x]=sumv[lc(x)]+sumv[rc(x)]+val[x];
	}
	inline void down(int x) {
		if(rev[x]) {
			reverse(lc(x));
			reverse(rc(x));
			rev[x]=0;
		}
		if(mark[x]) {
			NaCly_Fish_Orz(lc(x));
			NaCly_Fish_Orz(rc(x));
			mark[x]=0;
		}
	}
	inline int nrt(int x) {
		return x==lc(fa[x])||x==rc(fa[x]);
	}
	void psa(int x) {
		if(nrt(x)) psa(fa[x]);
		down(x);
	}
	inline void rotate(int x) {
		int y(fa[x]),z(fa[y]),k(x==rc(y));
		ch[y][k]=ch[x][k^1],ch[x][k^1]=y;
		if(nrt(y)) ch[z][y==rc(z)]=x;
		if(ch[y][k]) fa[ch[y][k]]=y;
		fa[y]=x,fa[x]=z,up(y);
	}
	inline void splay(int x) {
		int y,z;
		for(psa(x);nrt(x);rotate(x)) {
			y=fa[x],z=fa[y];
			if(nrt(y)) rotate(x==rc(y)^y==rc(z)?x:y);
		} up(x);
	}
	inline void access(int x) {
		for(int y=0;x;x=fa[y=x]) {
			splay(x); rc(x)=y; up(x);
		}
	}
	inline void mrt(int x) {
		access(x); splay(x); reverse(x);
	}
	inline void link(int x,int y) {
		mrt(x); fa[x]=y;
	}
	inline void cut(int x,int y) {
		mrt(x); access(y); splay(y);
		fa[x]=lc(y)=0; up(y);
	}
}

namespace Pockets {
	int ch[N][2],fa[N],rev[N],val[N],sumv[N],st[N],num;
	inline void reverse(int x) {
		if(x) {
			swap(lc(x),rc(x));
			rev[x]^=1;
		}
	}
	inline void up(int x) {
		sumv[x]=sumv[lc(x)]+sumv[rc(x)]+val[x];
	}
	inline void down(int x) {
		if(rev[x]) {
			reverse(lc(x));
			reverse(rc(x));
			rev[x]=0;
		}
	}
	inline int nrt(int x) {
		return x==lc(fa[x])||x==rc(fa[x]);
	}
	void psa(int x) {
		if(nrt(x)) psa(fa[x]);
		down(x);
	}
	inline void rotate(int x) {
		int y(fa[x]),z(fa[y]),k(x==rc(y));
		ch[y][k]=ch[x][k^1],ch[x][k^1]=y;
		if(nrt(y)) ch[z][y==rc(z)]=x;
		if(ch[y][k]) fa[ch[y][k]]=y;
		fa[y]=x,fa[x]=z,up(y);
	}
	inline void splay(int x) {
		int y,z;
		for(psa(x);nrt(x);rotate(x)) {
			y=fa[x],z=fa[y];
			if(nrt(y)) rotate(x==rc(y)^y==rc(z)?x:y);
		} up(x);
	}
	inline void access(int x) {
		for(int y=0;x;x=fa[y=x]) {
			splay(x); rc(x)=y; up(x);
		}
	}
	inline void mrt(int x) {
		access(x); splay(x); reverse(x);
	}
	inline void link(int x,int y) {
		mrt(x); fa[x]=y;
	}
	inline void cut(int x,int y) {
		mrt(x); access(y); splay(y);
		fa[x]=lc(y)=0; up(y);
	}
	void print(int now) {
		if(now) {
			down(now);
			print(lc(now));
			st[++num]=now;
			print(rc(now));
		}
	}
}

int n,q,opt,u,v,last,tot,ans,SummerPockets;

int fa[N];
inline int find(int x) {
	return x==fa[x]?x:fa[x]=find(fa[x]);
}

inline void getEdge(int u,int v) {
	int x=find(u),y=find(v);
	if(x!=y) {
		ans=-1;
		return;
	}
	Summer::mrt(u);
	Summer::access(v);
	Summer::splay(v);
	ans=Summer::sumv[v];
}

inline void getPoint(int u,int v) {
	int x=find(u),y=find(v);
	if(x!=y) {
		ans=-1;
		return;
	}
	Pockets::mrt(u);
	Pockets::access(v);
	Pockets::splay(v);
	ans=Pockets::sumv[v];
}

inline void link(int u,int v) {
	int x=find(u),y=find(v);
	if(x==y) {
		Summer::mrt(u);
		Summer::access(v);
		Summer::splay(v);
		Summer::NaCly_Fish_Orz(v);
		
		getPoint(u,v);
		if(ans>2) {
			++SummerPockets;
			Pockets::mrt(u);
			Pockets::access(v);
			Pockets::splay(v);
			Pockets::num=0;
			Pockets::print(v);
			for(int i=1;i<Pockets::num;++i)
				Pockets::cut(Pockets::st[i],Pockets::st[i+1]);
			for(int i=1;i<=Pockets::num;++i)
				Pockets::link(Pockets::st[i],SummerPockets);
		}
	} else {
		++tot; fa[y]=x;
		Summer::val[tot]=1;
		Summer::link(u,tot);
		Summer::link(tot,v);
		
		Pockets::link(u,v);
	}
}

int main() {
	scanf("%d%d",&n,&q);
	tot=SummerPockets=n;
	for(int i=1;i<=n;++i)
		fa[i]=i,Pockets::val[i]=1;
	while(q--) {
		scanf("%d%d%d",&opt,&u,&v);
		u^=last,v^=last;
		switch(opt) {
			case 1: {
				link(u,v);
				break;
			}
			case 2: {
				getEdge(u,v);
				if(ans!=-1) last=ans;
				printf("%d\n",ans);
				break;
			}
			default: {
				getPoint(u,v);
				if(ans!=-1) last=ans;
				printf("%d\n",ans);
				break;
			}
		}
	}
	return 0;
}