刚学LCT3day的萌新求助
查看原帖
刚学LCT3day的萌新求助
200044
JS_TZ_ZHR楼主2021/1/10 21:54

RT,不知道哪里错了

#include<bits/stdc++.h>
#define N 2000005
using namespace std;
int n,m;
struct Link_Cut_Tree {
	int f[N],s[N][2],tag[N];
	int get(int p) {
		return(p==s[f[p]][1]);
	}
	int isroot(int p) {
		return(p!=s[f[p]][0]&&p!=s[f[p]][1]);
	}
	void upd1(int p) {
		if(!p)return;
		tag[p]^=1;
		swap(s[p][0],s[p][1]);
	}
	void push_down(int p) {
		if(tag[p]) {
			upd1(s[p][0]);
			upd1(s[p][1]);
		}
		tag[p]=0;
	}
	void spin(int x) {
		int y=f[x],z=f[f[x]],opt=get(x);
		if(!isroot(y))s[z][get(y)]=x;
		s[y][opt]=s[x][opt^1],f[s[x][opt^1]]=y;
		s[x][opt^1]=y;
		f[y]=x,f[x]=z;
	}
	void upd2(int p) {
		if(!isroot(p))upd2(f[p]);
		push_down(p);
	}
	void splay(int x) {
		upd2(x);
		for(int fa=0; !isroot(x),fa=f[x]; spin(x))
			if(!isroot(fa))spin(get(fa)==get(x)?fa:x);
	}
	void access(int x) {
		for(int fa=0; x; fa=x,x=f[x])
			splay(x),s[x][1]=fa;
	}
	void link(int x,int y) {
		makeroot(x);
		f[x]=y;
	}
	void makeroot(int x) {
		access(x),splay(x),upd1(x);
	}
	void spilt(int x,int y) {
		makeroot(x),access(y),splay(y);
	}
	 int find(int p) {
        access(p),splay(p);
        while(s[p][0])push_down(p),p=s[p][0];
        splay(p);
        return p;
    }
	void cut(int x,int y) {
		spilt(x,y);
		f[x]=s[y][0]=0;
	}
	string query(int x,int y) {
		//spilt(x,y);
		if(find(x)==find(y))return "Yes";
		return "No";
	}
} t;
int main() {
	cin>>n>>m;
	string opt;
	int x,y;
	while(m--) {
		cin>>opt>>x>>y;
		if(opt=="Query")
			cout<<t.query(x,y)<<endl;
		else if(opt=="Connect")
			t.link(x,y);
		else
			t.cut(x,y);
	}
}
2021/1/10 21:54
加载中...