一个没有维护任何东西的动态树模板

忘了怎么写可以直接来粘

int ch[300010][2], fa[300010], st[300010];

bool lazy[300010];

bool nroot(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }

void rev(int x) { swap(ch[x][0], ch[x][1]), lazy[x] ^= 1; }

void pushup(int x) { /*维护一个pre*/ }

void pushdown(int x)

{

	if (lazy[x])

	{

		if (ch[x][0]) rev(ch[x][0]);

		if (ch[x][1]) rev(ch[x][1]);

		lazy[x] = 0;

	}

}

void rotate(int x)

{

	int y = fa[x], z = fa[y], k = ch[y][1] == x, w = ch[x][k ^ 1];

	if (nroot(y)) { ch[z][ch[z][1] == y] = x; } ch[x][k ^ 1] = y, ch[y][k] = w;

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

}

void splay(int x)

{

	int y = x, top = 0;

	st[++top] = y;

	while (nroot(y)) st[++top] = y = fa[y];

	while (top > 0) pushdown(st[top--]);

	while (nroot(x))

	{

		int y = fa[x], z = fa[y];

		if (nroot(y)) rotate((ch[y][1] == x) ^ (ch[z][1] == y) ? x : y);

		rotate(x);

	}

	pushup(x);

}

void access(int x)

{

	for (int y = 0; x > 0; x = fa[y = x])

		splay(x), ch[x][1] = y, pushup(x);

}

void makert(int x)

{

	access(x), splay(x), rev(x);

}

int findrt(int x)

{

	access(x), splay(x);

	while (ch[x][0]) pushdown(x), x = ch[x][0];

	return x;

}

void link(int x, int y)

{

	makert(x);

	if (findrt(y) != x) fa[x] = y;

}

void cut(int x, int y)

{

	makert(x);

	if (findrt(y) == x && fa[x] == y && ch[x][1] == 0)

		ch[y][0] = fa[x] = 0, pushup(y);

}

upd:压行Link-Cut Tree模板

bool nroot(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }

void rev(int x) { swap(ch[x][0], ch[x][1]), lazy[x] ^= 1; }

void pushup(int x) { /*维护一个pre*/ }

void pushdown(int x) { if (lazy[x]) { if (ch[x][0]) { rev(ch[x][0]); } if (ch[x][1]) { rev(ch[x][1]); } lazy[x] = 0; } }

void rotate(int x)

{

	int y = fa[x], z = fa[y], k = ch[y][1] == x, w = ch[x][k ^ 1];

	if (nroot(y)) { ch[z][ch[z][1] == y] = x; } ch[x][k ^ 1] = y, ch[y][k] = w;

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

}

void splay(int x)

{

	int y = x, top = 0; st[++top] = y; while (nroot(y)) { st[++top] = y = fa[y]; } while (top > 0) { pushdown(st[top--]); }

	while (nroot(x)) { int y = fa[x], z = fa[y]; if (nroot(y)) { rotate((ch[y][1] == x) ^ (ch[z][1] == y) ? x : y); } rotate(x); }

}

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

void makert(int x) { access(x), splay(x), rev(x); }

int findrt(int x) { access(x), splay(x); while (ch[x][0]) { pushdown(x), x = ch[x][0]; } return x; }

void link(int x, int y) { makert(x); if (findrt(y) != x) fa[x] = y; }

void cut(int x, int y) { makert(x); if (findrt(y) == x && fa[x] == y && ch[x][1] == 0) ch[y][0] = fa[x] = 0, pushup(y); }