动态树之 Link Cut Tree 学习笔记

LCT 题单做题记录

一、维护链信息

• P3203 [HNOI2010]弹飞绵羊：维护一条路径的长度，由于题目大大降低了难度，所以只需要使用 /(access/) 和 /(splay/) 两个操作即可。要学会灵活应用 LCT 中的函数，不要有刻板思维（如改变 /(cut/) 函数的写法）。

• P1501 [国家集训队]Tree II：需要维护加标记、乘标记和翻转标记三个 /(lazytag/)。/(pushdown/) 时，先处理乘的标记，再处理加的，最后处理翻转的。注意每次区间乘的时候该区间的加标记也要乘上该数。

• P4332 [SHOI2014]三叉神经树：【LG-P4332 [SHOI2014]】三叉神经树 题解 by 531

二、动态维护连通性&双联通分量

• P2542 [AHOI2005] 航线规划：离线倒序处理操作。对于连接后成环的两个节点，把其中一个 /(makeroot()/)，然后缩点——每个其子树内节点的并查集父亲赋为此点编号，此点与儿子断开连接。此时这个点代表着它和它儿子们组成的一个点双连通分量（成环）。那么若查询两个节点间的“关键航线”，就是 /(split()/) 它们两个各自的并查集祖先。

• 【DSY1664/BZOJ2959】长跑：题目中虽然说“没有给定每条单向边的方向，自行选择边的方向”，但是我们可以发现对于一个强连通分量，我们肯定都会走一遍，所以又变成了和上面航线规划一样的缩点了，每次查询还是 /(split()/) 它俩的代表节点，然后直接输出分裂出的子树的总和即可。

三、维护子树信息

• P4219 [BJOI2014]大融合：其实一眼就能看出大概思路，关键在于维护每个节点的 /(exsize/)，即和该节点以虚边相连的儿子数，具体只要在 /(access/) 和 /(link/) 中多一步更新 /(exsize/) 即可。

LCT 板子代码

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(register int i = a; i <= b; ++i)
#define ls t[x].ch[0]
#define rs t[x].ch[1]
const int maxn = 3e5 + 5;
int n, m;
struct node{
	int f, ch[2], sum, val;
	bool rev;
}t[maxn];

inline bool nrt(int p)
{
	int x = t[p].f;
	return (ls == p or rs == p);
}

inline void up(int x) {t[x].sum = t[ls].sum ^ t[rs].sum ^ t[x].val;}

inline void rv(int x) {swap(ls, rs); t[x].rev ^= 1;}

inline void dw(int x)
{
	if(!t[x].rev) return;
	if(ls) rv(ls); if(rs) rv(rs);
	t[x].rev = 0;
}

inline void rotate(int x)
{
	int y = t[x].f, z = t[y].f;
	int kx = (t[y].ch[1] == x), ky = (t[z].ch[1] == y), w = t[x].ch[!kx];
	if(nrt(y)) t[z].ch[ky] = x;
	t[x].ch[!kx] = y, t[y].ch[kx] = w;
	if(w) t[w].f = y;
	t[y].f = x, t[x].f = z;
	up(y), up(x);
}

inline void pushall(int x) {if(nrt(x)) pushall(t[x].f); dw(x);}

inline void splay(int x)
{
	pushall(x);
	while(nrt(x))
	{
		int y = t[x].f, z = t[y].f;
		if(nrt(y)) rotate((t[z].ch[1] == y) ^ (t[y].ch[1] == x) ? x : y);
		rotate(x);
	}
	up(x);
}

inline void access(int x)
{
	for(register int lst = 0; x; x = t[lst = x].f)
		splay(x), rs = lst, up(x);
}

inline void mkrt(int x) {access(x), splay(x), rv(x);}

inline int fndrt(int x)
{
	access(x), splay(x);
	while(ls) dw(x), x = ls;
	splay(x); return x;
}

inline void split(int x, int y) {mkrt(x), access(y), splay(y);}

inline void link(int x, int y) {mkrt(x); if(fndrt(y) != x) t[x].f = y;}

inline void cut(int x, int y)
{
	split(x, y);
	if(fndrt(y) == x and t[y].f == x and !t[y].ch[0])
		t[y].f = t[x].ch[1] = 0, up(x);
}

int main()
{
	scanf("%d%d", &n, &m);
	rep(i, 1, n) scanf("%d", &t[i].val);
	rep(i, 1, m)
	{
		int opt, x, y;
		scanf("%d%d%d", &opt, &x, &y);
		if(!opt) split(x, y), printf("%d/n", t[y].sum);
		if(opt == 1) link(x, y);
		if(opt == 2) cut(x, y);
		if(opt == 3) splay(x), t[x].val = y;
	}
	return 0;
}