Luogu P3690【模板】Link Cut Tree （LCT板题）

省选前刷道LCT板题(话说之前没做这道题…)

CODE

#include<bits/stdc++.h>

using namespace std;

inline void read(int &num) {

	char ch; int flg = 1; while(!isdigit(ch=getchar()))if(ch=='-')flg = -flg;

	for(num=0; isdigit(ch); num=num*10+ch-'0', ch=getchar()); num*=flg;

}

const int MAXN = 100005;

const int mod = 51061;

namespace LCT {

	#define ls ch[x][0]

	#define rs ch[x][1]

	int ch[MAXN][2], fa[MAXN], w[MAXN], sum[MAXN];

	bool rev[MAXN];

	inline bool isr(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }

	inline bool get(int x) { return ch[fa[x]][1] == x; }

	inline void upd(int x) { sum[x] = sum[ls] ^ sum[rs] ^ w[x]; }

	inline void mt(int x) { if(rev[x]) rev[ls]^=1, rev[rs]^=1, rev[x]^=1, swap(ls, rs); }

	void mtpath(int x) { if(!isr(x)) mtpath(fa[x]); mt(x); }

	inline void rot(int x) {

		int y = fa[x], z = fa[y]; bool l = get(x), r = l^1;

		if(!isr(y)) ch[z][get(y)] = x;

		fa[ch[x][r]] = y; fa[y] = x; fa[x] = z;

		ch[y][l] = ch[x][r]; ch[x][r] = y;

		upd(y), upd(x);

	}

	inline void splay(int x) {

		mtpath(x);

		for(; !isr(x); rot(x))

			if(!isr(fa[x])) rot(get(fa[x])==get(x)?fa[x]:x);

	}

	inline int access(int x) { int y = 0;

		for(; x; x=fa[y=x]) splay(x), ch[x][1] = y, upd(x);

		return y;

	}

	inline void bert(int x) { access(x), splay(x), rev[x]^=1; }

	inline int sert(int x) { access(x), splay(x); int y = x; for(; ch[x][0]; x=ch[x][0]); splay(x), splay(y); return x; }

	inline void Link(int x, int y) { bert(x); if(sert(y) != x) fa[x] = y; }

	inline void Cut(int x, int y) { bert(x); if(sert(y) == x && fa[x] == y && !ch[x][1]) fa[x] = ch[y][0] = 0, upd(y); }

	inline int split(int x, int y) { bert(x), access(y), splay(y); return y; }

	inline void Modify(int x, int val) { bert(x), w[x] = val, upd(x); }

	inline int Query(int x, int y) { return sum[split(x, y)]; }

	#undef ls

	#undef rs

}

using namespace LCT;

int n, q;

int main() {

	//freopen("sample.txt", "r", stdin);

	read(n), read(q);

	for(int i = 1; i <= n; ++i)

		read(w[i]), sum[i] = w[i];

	int op, x, y;

	while(q--) {

		read(op), read(x), read(y);

		switch(op) {

			case 0: printf("%d\n", Query(x, y)); break;

			case 1: Link(x, y); break;

			case 2: Cut(x, y); break;

			case 3: Modify(x, y); break;

		}

	}

}