Link cut tree

从名字中可以看出，这是一棵可以link和cut的树，也就是一棵动态树，准确来说是森林，支持树的链接与断裂，还要维护一些树上信息，例如节点间最大值，到根节点距离等

如果这棵树是静态的，那么用树剖+线段树就可以秒了，但动态的怎么办？

这就要用到Link cut tree了

Link cut tree借鉴于树链剖分的思想，将树划分为重链与轻链，而且是可以改变的轻重链，对于每一条重链，用splay进行维护【辅助树】，在splay中，以深度为标准，也就是说，左子树的节点都是u的上面的节点，u右子树的节点都是u下边的节点

主要包含以下操作：

Splay(u) 将u伸展到其所在辅助树的根

Access(u) 将根节点到u划分为重链

Make_root(u) 将u设为根

Link(u,v) 将u所在的树以u为根连到v上

Cut(u,v) 断开u,v的连边

Operate(u,v) 进行u到v路径上的操作

我们来分别讨论每一个操作如何实现

结构储存

在谈操作前，我们先看看我们需要储存的数据：

e[u].f u节点的父亲【若u不为辅助树的根，那么e[u].f表示u在辅助树中的父亲，否则表示该u所在整条重链的父亲】

e[u].ch[] u节点在辅助树中的儿子

e[u].rev 翻转标记

e[u].w 权值

还有各种标记与各种权值。。

struct node{
	int f,ch[2],rev,Max,plus,w;
	inline void Init() {f = ch[0] = ch[1] = rev = plus = 0;}
}e[maxn];

Splay操作

基本上是一样的，只不过要注意根节点的判定要看看父亲认不认这个儿子而不是看这个儿子有没有父亲。

除原树根节点外，每个节点都是有父亲的，也就是说儿子都认父亲，但是父亲不一定认儿子

inline void push_down(int u){
int i = 0;
do {temp[++i] = u;} while(!isrt(u) && (u = e[u].f));
while (i) pd(temp[i--]);
}
inline void spin(int u){
int s = isr(u),fa = e[u].f;
e[u].f = e[fa].f;
if (!isrt(fa)) e[e[fa].f].ch[isr(fa)] = u;
e[fa].ch[s] = e[u].ch[s^1];
if (e[u].ch[s^1]) e[e[u].ch[s^1]].f = fa;
e[fa].f = u;
e[u].ch[s^1] = fa;
push_up(fa);
}
inline void splay(int u){
push_down(u);
while (!isrt(u)){
if (isrt(e[u].f)) spin(u);
else if (isr(u) ^ isr(e[u].f)) spin(u),spin(u);
else spin(e[u].f),spin(u);
}
push_up(u);
}

大家可能会发现一个细节，就是每次spin之后只将fa进行更新，u节点不用么？

由于u是不断往上的，所以u放在结束时在push_up也是一样的，减少了push_up的次数

Access操作

Access操作是Link cut tree的核心，几乎Link cut tree的所有操作都是建立在Access的基础之上的

将u到根节点划为重链，每次将u伸展到根，同时将往上的父节点伸展到它所在的树的根，用u代替父节点的有儿子，这样子以往这条路径上的链断开，重连为u到根节点的链。要注意的是第一次时u往下的重链要断开

inline void Access(int u){
	for (int v = 0; u; u = e[v = u].f){
		splay(u);
		e[u].ch[1] = v;
		if (v) e[v].f = u;
		push_up(u);
	}
}

这个循环写的也是非常巧妙

Make_root操作

将u节点变为根，我们首先进行一次Access，这样根节点与u同在一个辅助树中，再将u伸展到根，翻转一下，u没有左儿子，所以u的深度就变为最小了【即为根】

inline void Make_root(int u){
	Access(u); splay(u);
	e[u].rev ^= 1;
}

是不是极为简洁？

Link操作

要将u节点接在v节点下边，首先先将u作为它所在原树的根节点【make_root】，再将v进行一次Access并伸展到根，这样一来v的右儿子一定是空的，直接连就好了

inline void Link(int u,int v){
	Make_root(u); Access(v); splay(v);
	e[u].f = v;
	e[v].ch[1] = u;
	push_up(v);
}

Cut操作

Cut操作将u和v断开，首先这个操作保证u和v是相邻的，将u作为根，v节点Access后伸展到根【发现没有，几乎所有的操作都是这个模式】，这个时候u一定在v的左边，断开左儿子就好了

inline void Cut(int u,int v){
	Make_root(u); Access(v); splay(v);
	int ls = e[v].ch[0];
	e[v].ch[0] = 0;
	e[ls].f = 0;
	push_up(v);
}

如果u与v并不相邻，那么这个操作的实质就是在以u为根的树中将以v为根的子树断开出来

Operate操作

这个操作比较广泛，因题而异，不过基本思路是相同的，都是先以u为根，再对v进行Access+splay，然后从v一直向左儿子走的路径就是v到u的路径，想要什么操作就可以进行了，一般都是借助之前维护好的一些值，例如树的大小siz,那么v左子树的大小就是v到u的距离

inline int Operate(int u,int v){
	Make_root(u); Access(v); splay(v);
	return e[v].siz;
}

练手的题

这个时候我们就可以轻松地“弹飞绵羊”啦~

BZOJ2002: [Hnoi2010]Bounce 弹飞绵羊

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define isr(x) (e[e[x].f].ch[1]==x)
#define isrt(x) (!e[x].f||(x!=e[e[x].f].ch[0]&&x!=e[e[x].f].ch[1]))
#define LL long long int
using namespace std;
const int maxn=400005,INF=2000000000,P=1000000007;

inline int read(){
	int out=0,flag=1;char c=getchar();
	while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
	while(c>=48&&c<=57){out=out*10+c-48;c=getchar();}
	return out*flag;
}

int N,M,RT,val[maxn];

struct node{
	int siz,f,ch[2],rev;
	node(){siz = 1;f = ch[0] = ch[1] = rev = 0;}
}e[maxn];

inline void pu(int u){e[u].siz = e[e[u].ch[0]].siz+e[e[u].ch[1]].siz+1;}

inline void pd(int u){
	if(e[u].rev){
		swap(e[u].ch[0],e[u].ch[1]);
		e[e[u].ch[0]].rev^=1;
		e[e[u].ch[1]].rev^=1;
		e[u].rev=0;
	}
}

inline void pushdown(int u){
	if(e[u].f&&!isrt(u)) pushdown(e[u].f);
	pd(u);
}

inline void spin(int u){
	int s = isr(u),fa = e[u].f;
	e[u].f = e[fa].f;
	if (e[fa].f&&!isrt(fa)) e[e[fa].f].ch[isr(fa)] = u;
	e[fa].ch[s] = e[u].ch[s^1];
	if (e[u].ch[s^1]) e[e[u].ch[s^1]].f = fa;
	e[u].ch[s^1] = fa;
	e[fa].f = u;
	pu(fa);pu(u);
}

inline void splay(int u){
	pushdown(u);
	while(!isrt(u)){
		if(isrt(e[u].f)) spin(u);
		else if(isr(u)^isr(e[u].f)) spin(u),spin(u);
		else spin(e[u].f),spin(u);
	}
}

inline void access(int u){
	for (int v = 0; u; u=e[v=u].f){
		splay(u);
		e[u].ch[1]=v;
		if(v) e[v].f=u;
		pu(u);
	}
}

void make_root(int u){
	access(u);splay(u);
	e[u].rev^=1;
}

void link(int u,int v){
	make_root(u);e[u].f=v;
}

void cut(int u,int v){
	make_root(u);access(v);splay(v);
	e[u].f=0;e[v].ch[0]=0;pu(v);
}

inline int Select(int u,int v){
	make_root(u);access(v);splay(v);
	return e[v].siz;
}

void init(){
	e[0].siz = 0;
	N = read();
	RT = N+1;
	int x;
	for (int i = 1; i <= N; i++){
		x = read();
		e[i].f = val[i] = (i+x>N ? RT:i+x);
	}
}

void solve(){
	int Q = read(),cmd,x,y;
	while(Q--){
		cmd = read();x = read() + 1;
		if (cmd&1){
			printf("%d
",Select(x,RT)-1);
		}else {
			y = read();
			cut(x,val[x]);
			link(x,(x+y>N ? RT:x+y));
			val[x]=(x+y>N ? RT:x+y);
		}
	}
}

int main(){
	init();
	solve();
	return 0;
}

再来一道板题：

HDU4010Query on The Trees

维护最大值

#include<iostream>
#include<cstdio>
#include<cstring>
#define isr(u) (e[e[u].f].ch[1]==u)
#define isrt(u) (!e[u].f || (e[e[u].f].ch[0] != u && e[e[u].f].ch[1] != u))
#define max(a,b) (a > b ? (a):(b))
using namespace std;
const int maxn=400005,maxm=1000005,INF=200000000;

inline int read(){
	int out = 0,flag = 1;char c = getchar();
	while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
	while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}
	return out*flag;
}

int N,Q,temp[maxn];

int head[maxn],nedge = 0;
struct EDGE{
	int to,next;
}edge[maxm];

inline void build(int u,int v){
	edge[nedge] = (EDGE){v,head[u]};
	head[u] = nedge++;
	edge[nedge] = (EDGE){u,head[v]};
	head[v] = nedge++;
}

struct node{
	int f,ch[2],rev,Max,plus,w;
	inline void Init() {f = ch[0] = ch[1] = rev = plus = 0;}
}e[maxn];

void Build(int u,int fa){
	e[u].f = fa;
	for (int k = head[u]; k != -1; k = edge[k].next)
		if(edge[k].to != fa)
			Build(edge[k].to,u);
}

inline bool judge(int u,int v){
	while (e[u].f) u = e[u].f;
	while (e[v].f) v = e[v].f;
	return u == v;
}

inline void push_up(int u){
	e[u].Max = max(e[u].w,max(e[e[u].ch[0]].Max,e[e[u].ch[1]].Max));
}

inline void pd(int u){
	if (e[u].rev){
		swap(e[u].ch[0],e[u].ch[1]);
		e[e[u].ch[0]].rev ^= 1;
		e[e[u].ch[1]].rev ^= 1;
		e[u].rev = 0;
	}
	if(e[u].plus){
		if(e[u].ch[0]){
			e[e[u].ch[0]].Max += e[u].plus;
			e[e[u].ch[0]].w += e[u].plus;
			e[e[u].ch[0]].plus += e[u].plus;
		}
		if(e[u].ch[1]){
			e[e[u].ch[1]].Max += e[u].plus;
			e[e[u].ch[1]].w += e[u].plus;
			e[e[u].ch[1]].plus += e[u].plus;
		}
		e[u].plus = 0;
	}
}

inline void push_down(int u){
	int i = 0;
	do {temp[++i] = u;} while(!isrt(u) && (u = e[u].f));
	while (i) pd(temp[i--]);
}

inline void spin(int u){
	int s = isr(u),fa = e[u].f;
	e[u].f = e[fa].f;
	if (!isrt(fa)) e[e[fa].f].ch[isr(fa)] = u;
	e[fa].ch[s] = e[u].ch[s^1];
	if (e[u].ch[s^1]) e[e[u].ch[s^1]].f = fa;
	e[fa].f = u;
	e[u].ch[s^1] = fa;
	push_up(fa);
}

inline void splay(int u){
	push_down(u);
	while (!isrt(u)){
		if (isrt(e[u].f)) spin(u);
		else if (isr(u) ^ isr(e[u].f)) spin(u),spin(u);
		else spin(e[u].f),spin(u);
	}
	push_up(u);
}

inline void Access(int u){
	for (int v = 0; u; u = e[v = u].f){
		splay(u);
		e[u].ch[1] = v;
		if (v) e[v].f = u;
		push_up(u);
	}
}

inline void Make_root(int u){
	Access(u); splay(u);
	e[u].rev ^= 1;
}

inline void Link(int u,int v){
	if (judge(u,v)){
		puts("-1");
		return;
	}
	Make_root(u); Access(v); splay(v);
	e[u].f = v;
	e[v].ch[1] = u;
	push_up(v);
}

inline void Cut(int u,int v){
	if (u == v||!judge(u,v)){
		puts("-1");
		return;
	}
	Make_root(u); Access(v); splay(v);
	int ls = e[v].ch[0];
	e[v].ch[0] = 0;
	e[ls].f = 0;
	push_up(v);
}

inline void Change(int u,int v,int w){
	if(!judge(u,v)){
		puts("-1");
		return;
	}
	Make_root(u); Access(v); splay(v);
	e[v].Max += w;
	e[v].w += w;
	e[v].plus += w;
}

inline int Query(int u,int v){
	if(!judge(u,v)) return -1;
	Make_root(u); Access(v); splay(v);
	return e[v].Max;
}

void init(){
	memset(head,-1,sizeof(head));
	nedge = 0;
	e[0].Max = e[0].w = -1;
	for (int i = 1; i <= N; i++) e[i].Init();
	for (int i = 1; i < N; i++) build(read(),read());
	Build(1,0);
	for (int i = 1; i <= N; i++) e[i].Max = e[i].w = read();
}

void solve(){
	Q = read();
	int cmd,a,b,c;
	while (Q--){
		cmd = read();
		a = read();
		b = read();
		if (cmd == 1) Link(a,b);
		else if(cmd == 2) Cut(a,b);
		else if(cmd == 3){ c = read(); Change(b,c,a); }
		else printf("%d
",Query(a,b));
	}
}

int main()
{
	while (cin >> N){
		init();
		solve();
		printf("
");
	}
	return 0;
}