#include<algorithm>
#include<cctype>
#include<cstdio>
#define rit register int
#define ric register char
#pragma GCC optimize(3)

using namespace std;

////IO////

inline int fr(){
	rit val=0,sig=1;ric tp=getchar();
	while(!isdigit(tp))tp=getchar();
	while(isdigit(tp)){
		val=(val<<3)+(val<<1)+tp-'0';
		tp=getchar();
	}
	return val*sig;
}

//////////


//////////Splay//////////

#define l(x) dat[x].s[0]
#define r(x) dat[x].s[1]
#define fa(x) dat[x].fa
#define ink(x) dat[x].ink
#define sz(x) dat[x].siz
#define tag(x) dat[x].tag
#define pla(x) dat[x].pla

struct node{
	int s[2],fa,ink,siz,tag,pla;
}dat[200010];

void pushup(int x){
	sz(x)=sz(l(x))+sz(r(x))+1;
}

bool isrc(int x){
	return r(fa(x))==x;
}

int getfa(int x){
	while(fa(x)&&ink(fa(x)))fa(x)=ink(fa(x));
	return fa(x);
}

bool isrt(int x){
	return (!getfa(x))||(l(getfa(x))!=x&&r(getfa(x))!=x);
}

void pushdown(int x){
	if(tag(x)){
		swap(l(x),r(x));
		if(l(x))tag(l(x))^=tag(x);
		if(r(x))tag(r(x))^=tag(x);
		tag(x)=0;
	}
}

void update(int x){
	if(!isrt(x))update(getfa(x));
	pushdown(x);
}

void rotate(int x){
	int fa=getfa(x),gfa=getfa(getfa(x));
	bool g=isrc(x);
	if(!isrt(fa))dat[gfa].s[isrc(fa)]=x;
	fa(x)=gfa;
	dat[fa].s[g]=dat[x].s[!g];
	fa(dat[fa].s[g])=fa;
	dat[x].s[!g]=fa;
	fa(fa)=x;
	pushup(fa);pushup(x);
}

void splay(int x){
	update(x);
	while(!isrt(x)){
		int fa=getfa(x);
		if(!isrt(fa)){
			if(isrc(fa)^isrc(x))rotate(x);
			else rotate(fa);
		}
		rotate(x);
	}
}

///////////End///////////

///////////LCT///////////

int vis[200010];

void access(int x){
	if(vis[x])x=getfa(x);
	for(int y=0;x;y=x,x=getfa(x)){
		splay(x);r(x)=y;pushup(x);
	}
}

void makeroot(int x){
	if(vis[x])x=getfa(x);
	access(x);
	splay(x);
	tag(x)^=1;
}

int findroot(int x){
	if(vis[x])x=getfa(x);
	access(x);
	splay(x);
	while(l(x)){
		x=l(x);pushdown(x);
	}
	splay(x);
	return x;
}

void link(int x,int y){
	if(vis[x])x=getfa(x);
	if(vis[y])y=getfa(y);
	makeroot(x);
	splay(y);
	fa(x)=y;
}

void split(int x,int y){
	if(vis[x])x=getfa(x);
	if(vis[y])y=getfa(y);
	makeroot(x);
	access(y);splay(y);
}

///////////End///////////

/////////LCT-Rev/////////

void dfs(int x,int mk){
	if(x!=mk){
		ink(x)=mk;
		vis[x]=1;
		pla(mk)+=pla(x);
	}
	if(l(x))dfs(l(x),mk);
	if(r(x))dfs(r(x),mk);
}

void tarjan(int x,int y){
	if(vis[x])x=getfa(x);
	if(vis[y])y=getfa(y);
	split(x,y);
	dfs(y,y);
	sz(y)=1;l(y)=r(y)=0;
}

int operate(int x,int y){
	if(vis[x])x=getfa(x);
	if(vis[y])y=getfa(y);
	if(x==y)return pla(x);
	
	if(findroot(x)!=findroot(y))link(x,y);
	else{
		tarjan(x,y);
		return pla(y);
	}
	return -1;
}

///////////End///////////

// Kono LCT nanoda!

int n,m,p;

int main(){
	
	//freopen("8.in","r",stdin);
	//freopen("8.my","w",stdout);
	
	//ios::sync_with_stdio(false);
	//cin.tie(nullptr);
	
	//cin>>n>>m>>p;
	n=fr();m=fr();p=fr();
	
	for(int i=1;i<=n;i++){
		dat[i].pla=1;
	}
	
	int x,y;
	for(int i=1;i<=m;i++){
		//cin>>x>>y;
		x=fr();y=fr();
		int trash=operate(x,y);
	}
	
	for(int i=1;i<=p;i++){
		//cin>>x>>y;
		x=fr();y=fr();
		int ans=operate(x,y);
		if(ans==-1)puts("No");
		else printf("%d\n",ans);
	}
	
	return 0;	
}

题目：DKBZOJ-4998 星球联盟

现象描述：第8个点TLE，大约10秒才能跑完，答案没有任何问题。