#创作计划# LCT入门

KID2695

2025-10-23 15:44:55

发布于：山东

75阅读

0回复

0点赞

前言：里面的题都是洛谷的，没有对应到acgo上面，大家可以去原网站搜编号或者从acgo里找一找。

LCT
- 在有加删边的前提下进行链操作
- 链查询就是进行剖分后重组或拼装后经行计算
- LCT使用的是实链剖分
  - 一个节点只会向一个儿子连实边
  - 每一条实链都用一个splay去维护
  - 虚边就是连接两个splay的边
  - 实边就是儿子和父亲可以互相找
  - 虚边是只能儿子找父亲
接下来是LCT的一些操作
- access
  - 这个操作的意思是打通某个节点与根节点之间的路径，即变为一条实链。（这个操作也可以理解为把路径上每个节点到路径以外的实边变虚，到路径中的虚边变实。）
  - access就是循环进行以下操作
    - 点 $x$ 转到根
    - 点 $x$ 的右儿子挂上点 $y$ （虚实转换）
    - 更新点 $x$ 的信息
    - 点 $x$ 变为自己的父节点， $y$ 变为 $x$
  - access还有一个十分优雅的性质可以用来求LCA
    - 我们每次在最后的时候返回一下 $y$
    - 如果我们要求 $A$ $A$ 与 $B$ $B$ 的LCA，我们可以这么做
      - 先access一下 $A$
      - 然后access一下 B
      - 随后所返回的 $y$ 就是LCA
    - 证明的话还是感性理解一下
      - 如果 $B$ 位于根节点与 $A$ 的链上的话，最后一定返回的是 $B$
      - 否则最后一次离开虚边的时候所跳到的点一定是两点的LCA
- 关于splay
  - 这里的splay需要经行一些改动
  - 第一个是pushall操作的加入
    - 这个操作就是不断向上跳，跳到splay的根，然后pushdown下来
    - 时间复杂度均摊是log的，因为用完以后会splay
  - rotate也要改
    - 因为有虚边的原因，我们不能保证父亲的父亲节点仍在这颗splay中
    - 所以我们需要特判一下 $z$ 是否要向 $x$ 连一条边
  - splay也就需要跟着变
    - 由于我们rotate没有考虑父亲节点是否在同一颗splay中，所以我们只有在符合父子节点位于同一splay的时候才考虑单双旋
- makeroot
  - 当需要打通的两个点有一个点不是根的时候，我们就需要换根
  - acces(x）之后， $x$ 一定是splay中，中序遍历最后的点
  - 然后splay(x)， $x$ 变为了根，便于操作的同时保证了时间复杂度的正确性
  - 翻转整个Splay，使得所有点的深度都倒过来了， $x$ 没了左子树，反倒成了深度最小的点（根节点），达到了我们的目的
- split
  - 打通两个点之间的路径
  - 先makeroot一下 $x$
  - 然后access一下 $y$
  - 别忘了splay一下 $y$
  - 同时求链的答案也用这个
    - access完 $y$ 以后，它就是这条实链中原树中深度最大的点
    - splay完了它又是根
    - 所以输出一下 $y$ 所记录的答案就好了
- findroot
  - 用来找寻x所在原树的树根，可用于连通性的判断。
  - 我们可以先access，然后继续splay一下，这样找根方便时间复杂度也是正确的。
  - 不断走左儿子就能到达原树的根，最后不要忘了把根splay回去来保证复杂度
- link
  - 先把 $x$ 变为根，然后看一下 $y$ 的findroot是不是 $x$ 就知道需不需要连这条边了
  - 连边就是让 $x$ 的父节点变为 $y$
- cut
  - 考虑如何判断是否有边
    - 先makeroot一下 $x$ 然后 $y$ 的findroot需要是 $x$
    - 同时这两个点的深度一定要相邻
    - 也就是 $y$ 不能有左儿子， $y$ 的父节点一定是 $x$
  - 再考虑如何删边
    - makeroot完 $x$ 之后它一定没有了左儿子
    - 所以右儿子设为零， $y$ 的父亲变为0就好了

P3690：单点修改，链查询异或结果，填删边

板子题，直接做就好了

#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
#define fa(x) t[x].fa
#define notroot(x) (ls(fa(x))==x||rs(fa(x))==x)
struct LcT{
	void pushup(int x){
		return (void)(t[x].sum=t[ls(x)].sum^t[rs(x)].sum^t[x].val);
	}
	void push_down(int x){
		if(t[x].fla){
			swep(ls(x),rs(x));
			t[ls(x)].fla^=1;
			t[rs(x)].fla^=1;
			t[x].fla=0;
		}
	}
	void pushall(int x){
		if(notroot(x)) pushall(fa(x));
		push_down(x);
	}
	void rotate(int x){
		int y=fa(x),z=fa(y),op=rs(y)==x;
		if(notroot(y)) t[z].ch[rs(z)==y]=x;
		fa(x)=z;
		t[y].ch[op]=t[x].ch[op^1];
		fa(t[x].ch[op^1])=y;
		t[x].ch[op^1]=y;
		fa(y)=x;
		pushup(y);
		pushup(x);
	}
	void splay(int x){
		pushall(x);
		while(notroot(x)){
			int y=fa(x),z=fa(y);
			if(notroot(y)) (rs(y)==x)^(rs(z)==y) ? rotate(x) : rotate(y);
			rotate(x);
		}
	}
	void access(int x){
		for(int y=0;x;){
			splay(x);
			rs(x)=y;
			pushup(x);
			y=x;
			x=fa(x);
		}
	}
	void makeroot(int x){
		access(x);
		splay(x);
		t[x].fla^=1;
	}
	void split(int x,int y){
		makeroot(x);
		access(y);
		splay(y);
	}
	int find_root(int x){
		access(x);
		splay(x);
		while(ls(x)){
			push_down(x);
			x=ls(x);
		}
		splay(x);
		return x;
	}
	void link(int x,int y){
		makeroot(x);
		if(find_root(y)!=x) fa(x)=y;
	}
	void cut(int x,int y){
		makeroot(x);
		if(find_root(y)==x&&fa(y)==x&&!ls(y)){
			rs(x)=fa(y)=0;
			pushup(x);
		}
	}
	void output(int x,int y){
		split(x,y);
		printf("%d\n",t[y].sum);
	}
}cb;

单点修改之后别忘了splay一下

P3203：给定 n 个点和点权 $a_i$ ，绵羊在 i 处会被弹到 $i+a_i$ 位置，如果该位置大于 $n$ 则被弹飞，否则继续往后弹，求从一个位置弹几次会弹飞。同时还有单点的点权修改
- 发现单点的点权修改只会影响一个位置往后弹到哪里
- 所以我们经行连边，每个点向它弹到的那个点连边
- 弹飞的次数就是size了
- 单点修改权值就是重新连边了
P2147：同态判断两点是否连通
- 每次LCT直接findroot一下看是不是一样就好了
- 如果不是强制在线的话，我们还有别的做法
  - 可以线段树分治+可撤销并查集（便于实现，我们按树高合并）
P1501：修改一条边的两个端点，链乘，链加，链查询
- LCT直接维护就好了