LinkCutTree

FlashHu 巨佬的原理讲解 FlashHu 巨佬的应用讲解

维护链信息

洛谷P3690 【模板】Link Cut Tree 代码+注释
模板，多棵 ( t splay) 实链剖分，以原树中深度为 ( t BST) 关键字，可以动态树连边删边求链权。

HNOI2010 弹飞绵羊 代码
连边删边，通过维护 (sz) 求原树深度，不需要路径操作，所以可以不换根。

国家集训队 Tree II 代码
在普通的 ( t LinkCutTree) 上打懒标记，推标记，( t pushdown) 标记的顺序重要。

动态并查集

洛谷P3950 部落冲突 代码
用 ( t LinkCutTree) 动态维护并查集，不需要 ( t Pushup /qq)。

SDOI2008 洞穴勘测 代码
用 ( t LinkCutTree) 动态维护并查集，不需要 ( t Pushup /qq)，对，就是重题。

模板

//LinkCutTree
int fa[N],ch[N][2],val[N],re[N],q[N];
int notrt(int u){
	if(!~fa[u]) return 0;
	return ch[fa[u]][0]==u||ch[fa[u]][1]==u;
}
void pushup(int u){
	val[u]=a[u];
	if(~ch[u][0]) val[u]^=val[ch[u][0]];
	if(~ch[u][1]) val[u]^=val[ch[u][1]];
}
void pushre(int u){swap(ch[u][0],ch[u][1]),re[u]^=1;}
void pushdo(int u){
	if(!re[u]) return;
	if(~ch[u][0]) pushre(ch[u][0]);
	if(~ch[u][1]) pushre(ch[u][1]);
	re[u]=0;
}
void rotate(int u){
	int v=fa[u],w=fa[v],d=ch[v][1]==u,s=ch[u][!d];
	if(notrt(v)) ch[w][ch[w][1]==v]=u; ch[u][!d]=v,ch[v][d]=s;
	if(~s) fa[s]=v; fa[v]=u,fa[u]=w,pushup(v);
}
void splay(int u){
	int v=u,w=-1,qc=0; q[qc++]=v;
	while(notrt(v)) q[qc++]=v=fa[v];
	while(qc) pushdo(q[--qc]);
	while(notrt(u)){
		v=fa[u],w=fa[v];
		if(notrt(v)) rotate((ch[v][0]==u)^(ch[w][0]==v)?u:v);
		rotate(u);
	}
	pushup(u);
}
void access(int u){
	for(int s=-1;~u;u=fa[s=u])
		splay(u),ch[u][1]=s,pushup(u);
}
void bert(int u){access(u),splay(u),pushre(u);}
int findrt(int u){
	access(u),splay(u);
	while(~ch[u][0]) pushdo(u),u=ch[u][0];
	return splay(u),u;
}
void lift(int u,int v){bert(u),access(v),splay(v);}
void link(int u,int v){bert(u);if(findrt(v)!=u) fa[u]=v;}
void cut(int u,int v){
	bert(u);
	if(findrt(v)==u&&fa[v]==u&&!~ch[v][0])
		fa[v]=ch[u][1]=-1,pushup(u);
}

P.S.

• rotate