模板
\(\text{Code}\)

#include <cstdio>

#include <iostream>

#define IN inline

#define RE register

using namespace std;

const int N = 1e5 + 5;

int n, m;

struct LCT{

	int st[N], c[N][2], fa[N], v[N], s[N], tg[N];

	IN void pushup(int x){s[x] = s[c[x][0]] ^ s[c[x][1]] ^ v[x];}

	IN void reverse(int x){tg[x] ^= 1, swap(c[x][0], c[x][1]);}

	IN void pushdown(int x)

	{

		if (!tg[x]) return; tg[x] = 0;

		if (c[x][0]) reverse(c[x][0]);

		if (c[x][1]) reverse(c[x][1]);

	}

	IN int isroot(int x){return c[fa[x]][0] != x && c[fa[x]][1] != x;}

	IN void rotate(int x)

	{

		int y = fa[x], z = fa[y], k = (c[y][1] == x), w = c[x][!k];

		if (!isroot(y)) c[z][c[z][1] == y] = x; c[x][!k] = y, c[y][k] = w;

		if (w) fa[w] = y; fa[y] = x, fa[x] = z, pushup(y);

	}

	IN void splay(int x)

	{

		int y = x, z = 0; st[++z] = y;

		while (!isroot(y)) st[++z] = y = fa[y];

		while (z) pushdown(st[z--]);

		while (!isroot(x)){y=fa[x],z=fa[y]; if (!isroot(y)) rotate((c[y][0]==x)^(c[z][0]==y)?x:y); rotate(x);}

		pushup(x);

	}

	IN void access(int x){for(RE int y=0; x; y=x, x=fa[x]) splay(x), c[x][1] = y, pushup(x);}

	IN void makeroot(int x){access(x), splay(x), reverse(x);}

	IN int findroot(int x){access(x), splay(x); while (c[x][0]) pushdown(x),x=c[x][0]; splay(x); return x;}

	IN void split(int x, int y){makeroot(x), access(y), splay(y);}

	IN void link(int x, int y){makeroot(x); if (findroot(y)^x) fa[x] = y;}

	IN void cut(int x, int y){makeroot(x); if (findroot(y)==x&&fa[y]==x&&!c[y][0]) fa[y]=c[x][1]=0,pushup(x);}

}T;

int main()

{

	scanf("%d%d", &n, &m);

	for(RE int i = 1; i <= n; i++) scanf("%d", &T.v[i]);

	for(int op, x, y; m; --m)

	{

		scanf("%d%d%d", &op, &x, &y);

		if (op == 0) T.split(x, y), printf("%d\n", T.s[y]);

		else if (op == 1) T.link(x, y);

		else if (op == 2) T.cut(x, y);

		else T.splay(x), T.v[x] = y, T.pushup(x);

	}

}
巴特西

【模板】动态树（Link Cut Tree）

\(\text{Code}\)

最新文章

热门文章
