Link-Cut Tree是一种用于维护动态树的数据结构，由 Sleator 和 Tarjan 在 1983 年提出。
它支持在树的形态动态变化（加边、删边）的情况下，高效地维护树上路径信息。
动态性：支持树的动态连边和断边
高效性：所有操作均摊时间复杂度为 O(log n)
灵活性：可以维护路径上的各种信息（和、最大值、最小值等）
P3690 【模板】动态树（LCT） - 洛谷 (luogu.com.cn)
我们维护一颗Binary Search Tree（二叉搜索树），
保证操作前后它的中序遍历始终代表的是“原树中一条路径从上到下的深度顺序”。
0.先导-我们需要什么？
问题：
有一棵动态变化的树（可以加边、删边）
需要快速查询树上任意两点路径的信息
需要快速修改路径上的信息
传统方法：
树链剖分：树结构固定，无法处理动态变化
直接 DFS：每次操作，太慢
倍增法：不支持动态修改
换句话说，我们需要一种能 log 级别时间分离、合并、支持局部修改的结构维护树。
那为什么不用 Treap / 线段树，而用码量更大的 Splay？
因为 Splay 的根旋转操作会将查询的节点移到根，而动态树询问恰好就需要多次访问同一节点。
这样第一次操作时间复杂度为，后续只需
。
而 Treap 的每次操作都是，不利于局部操作。
线段树就只能维护静态结构，不能用于动态加删边。
1.框架-我们要求什么？
求路径上点异或和
删除、添加边
改变点权值
在 的询问下，单次暴力走树上路径最大
，不可。
如果将树拆成一条条链，单次查询链就是。
// 将一棵树分解成若干条不相交的路径 原树： 1 / \ 2 5 / \ \ 3 4 6 / 7 一种路径分解： 路径1：1-2-4-7 路径2：3 路径3：5-6假设查询 x 到 y 的路径，我们用 Splay 通过神秘操作将 x 旋转到树根。
问题就变成从根到固定点 y 的链操作了。
但链每次查询都会变，我们把当前查询的链称为“实链”，树上其他的边称为“虚链”，方便操作。
以下为标准的 Splay 旋转操作：
这是右旋，当 x 为 y 的左子树时进行，将 y 开始的整个子树整体向右旋转。
旋转后 x 称为原来 y 子树的根，y 是 x 的右子树。
y 的左子树则用 x 右子树代替。
这是左旋，当 x 为 y 的右子树时进行，将 y 开始的整个子树整体向左旋转。
旋转后 x 称为原来 y 子树的根，y 是 x 的左子树。
y 的右子树则用 x 左子树代替。
可以发现这两种旋转都没有改变树的中序遍历，即操作保序。
而且原来深度比 x 小的都在它左子树，深度比 x 大的都在它右子树。
这很有意思，因为树上路径就是 x - LCA - y，和中序遍历顺序相同。
所以我们使用 Splay 将 x 转为根节点时，到 y 的路径顺序却没变。
// 原树： 1 / \ 2 5 / \ \ 3 4 6 / 7 // 查询路径 4 → 6 // 步骤1：makeroot(4) // 4成为新根，树变成： 4 \ 2 / \ 1 3 \ 5 \ 6 / 7 // 步骤2：access(6) // 打通4到6的路径：4-2-1-5-6 // 这条路径成为实链 // 步骤3：splay(6) // 6成为Splay的根 // Splay中序遍历 = 4, 2, 1, 5, 6 // 这就是路径！旋转代码：
// rotate：旋转操作（核心） // 功能：将节点 x 向上旋转一层 // 参数：x 是要旋转的节点 // 注意：这是 Splay 的旋转，但处理了 LCT 的虚边 void rotate(int x){ int y = fa(x); // y 是 x 的父节点 int z = fa(y); // z 是 y 的父节点 int k = rc(y) == x; // k = 1 表示 x 是 y 的右儿子，k = 0 表示 x 是 y 的左儿子 // 关键：如果 y 不是 Splay 根，将 x 连接到 z if (notroot(y)) tr[z].ch[rc(z) == y] = x; fa(x) = z; // x 的父节点设为 z // 将 x 的相应儿子转移给 y tr[y].ch[k] = tr[x].ch[k^1]; fa(tr[x].ch[k^1]) = y; // y 变成 x 的儿子 tr[x].ch[k^1] = y; fa(y) = x; // 自底向上更新 pushup(y); pushup(x); }再来看看换根函数。
// splay：将节点 x 伸展到 Splay 的根 // 功能：通过旋转将 x 变为所在 Splay 的根 // 注意：会处理同向和异向的旋转 void splay(int x){ pushall(x); // 先下传所有标记 while(notroot(x)){ // 只要 x 不是 Splay 根 int y = fa(x), z = fa(y); if(notroot(y)){ // 如果 y 也不是根 // 如果 x 和 y 同向（都是左儿或都是右儿），先旋 y // 如果不同向，先旋 x (rc(y)==x) ^ (rc(z)==y) ? rotate(x) : rotate(y); } rotate(x); // 最后旋转 x } }当 x 和 y 是同向，此时如果按照异向时旋转 x，就会出现：
可以看到出现了链，即平衡树变得“不平衡”，违背了我们想 log 级别时间操作的初心。
但如果旋转 y 呢？
先让 y 做根，让链变成“二叉”，再旋转 x，完美的使单链结构成为二叉树！
2.整体-我们注意什么？
实际上，以上所述内容加起来不到 LCT 内容的 30%。
更多的，更细节的，我们需要联合整体来看。
回顾我们所需的操作与实际对应步骤：
求 x 到 y 路径上点异或和
1.打通 x 到根的路线，使其变成实链
2.将 x 换到根
3.中序遍历输出 x 到 y 的路径（直实链）
删除 x 到 y 边
1.打通 x 到根的路线，使其变成实链
2.将 x 换到根
3.如果 y 与 x 相连就断开其父指针
添加 x 到 y 边
1.打通 x 到根的路线，使其变成实链
2.将 x 换到根
3.如果 y 与 x 不相连就联系其父指针
改变点权值
1.打通 x 到根的路线，使其变成实链
2.将 x 换到根
3.更新根节点权值
#include <iostream> #include <cstring> #include <algorithm> using namespace std; #define N 300010 // 最大节点数 // 宏定义：简化代码书写 #define fa(x) tr[x].fa // 获取节点x的父节点 #define lc(x) tr[x].ch[0] // 获取节点x的左儿子 #define rc(x) tr[x].ch[1] // 获取节点x的右儿子 #define notroot(x) lc(fa(x))==x||rc(fa(x))==x // 判断x是否为Splay的根 int n,m; // n个节点，m个操作 struct node{ // LCT节点结构 int ch[2]; // 左右儿子（在Splay中） int fa; // 父节点（可能是Splay父，也可能是虚边） int v; // 节点权值 int sum; // 子树异或和（维护路径异或） int tag; // 翻转懒标记 }tr[N]; // pushup：更新节点信息 // 功能：用儿子信息更新父节点 // 用途：在旋转、修改后更新节点 void pushup(int x){ tr[x].sum = tr[lc(x)].sum ^ tr[x].v ^ tr[rc(x)].sum; // 异或和 = 左子树异或和 ^ 当前节点值 ^ 右子树异或和 } // pushdown：下传懒标记 // 功能：将翻转标记传递给子节点 // 调用时机：在访问子节点前必须调用 void pushdown(int x){ if(tr[x].tag){ // 如果有翻转标记 swap(lc(x), rc(x)); // 交换左右子树 tr[lc(x)].tag ^= 1; // 左子树标记翻转 tr[rc(x)].tag ^= 1; // 右子树标记翻转 tr[x].tag = 0; // 清除当前标记 } } // pushall：从根到当前节点依次下传标记 // 功能：确保从Splay根到x路径上所有标记都被下传 // 调用时机：在splay操作开始时 void pushall(int x){ if(notroot(x)) pushall(fa(x)); // 递归到Splay的根 pushdown(x); // 下传当前节点标记 } // rotate：旋转操作（核心） // 功能：将节点 x 向上旋转一层 // 参数：x 是要旋转的节点 // 注意：这是 Splay 的旋转，但处理了 LCT 的虚边 void rotate(int x){ int y = fa(x); // y 是 x 的父节点 int z = fa(y); // z 是 y 的父节点 int k = rc(y) == x; // k = 1 表示 x 是 y 的右儿子，k = 0 表示 x 是 y 的左儿子 // 关键：如果 y 不是 Splay 根，将 x 连接到 z if (notroot(y)) tr[z].ch[rc(z) == y] = x; fa(x) = z; // x 的父节点设为 z // 将 x 的相应儿子转移给 y tr[y].ch[k] = tr[x].ch[k^1]; fa(tr[x].ch[k^1]) = y; // y 变成 x 的儿子 tr[x].ch[k^1] = y; fa(y) = x; // 自底向上更新 pushup(y); pushup(x); } // splay：将节点 x 伸展到 Splay 的根 // 功能：通过旋转将 x 变为所在 Splay 的根 // 注意：会处理同向和异向的旋转 void splay(int x){ pushall(x); // 先下传所有标记 while(notroot(x)){ // 只要 x 不是 Splay 根 int y = fa(x), z = fa(y); if(notroot(y)){ // 如果 y 也不是根 // 如果 x 和 y 同向（都是左儿或都是右儿），先旋 y // 如果不同向，先旋 x (rc(y)==x) ^ (rc(z)==y) ? rotate(x) : rotate(y); } rotate(x); // 最后旋转 x } } // access：打通根到x的路径 // 功能：将根到x的路径变为实链 // 核心操作：LCT最重要的操作 void access(int x){ for(int y=0; x; ){ // y是上一次处理的节点 splay(x); // 将x旋转到Splay根 rc(x) = y; // x的右儿子设为y（建立实边） pushup(x); // 更新x的信息 y = x; // y向上移动 x = fa(x); // x沿着虚边向上 } } // makeroot：将x变为原树的根 // 功能：通过换根操作，使x成为整棵树的根 // 原理：access后翻转路径方向 void makeroot(int x){ access(x); // 打通根到x的路径 splay(x); // x转到Splay根 tr[x].tag ^= 1; // 翻转整个Splay } // split：提取x到y的路径 // 功能：将x到y的路径提取到一个Splay中 // 结果：路径在y的Splay中，y是Splay的根 void split(int x,int y){ makeroot(x); // x成为根 access(y); // 打通根到y的路径 splay(y); // y转到Splay根 } // output：输出路径异或和 // 功能：查询x到y路径上所有节点值的异或和 void output(int x,int y){ split(x,y); // 提取路径 printf("%d\n", tr[y].sum); // y的sum就是路径异或和 } // findroot：查找x所在原树的根 // 功能：找到x所在树的根节点 // 原理：access后，最左节点就是根 int findroot(int x){ access(x); // 打通根到x splay(x); // x转到Splay根 // 一直向左走，找到最左节点 while(lc(x)){ pushdown(x); // 下传标记，确保儿子正确 x = lc(x); } splay(x); // 将根转到Splay根（防止卡链） return x; } // link：连接两个节点 // 功能：在x和y之间加一条边 void link(int x,int y){ makeroot(x); // x成为根 if(findroot(y) != x) // 如果x和y不连通 fa(x) = y; // 添加虚边 } // cut：删除边 // 功能：删除x和y之间的边 void cut(int x,int y){ makeroot(x); // x成为根 // 检查y是否直接连接x if(findroot(y) == x && fa(y) == x && !lc(y)){ //findroot(y) == x：x和y在同一棵树（防止删不同树的节点） //fa(y) == x：y的父亲是x（防止删间接连接的节点） //!lc(y)：y没有左儿子（确保x和y之间没有其他节点，即直接相邻） fa(y) = 0; // 断开y的父指针 pushup(x); // 更新x的信息 } } // change：修改节点权值 // 功能：将节点x的权值修改为y void change(int x,int y){ splay(x); // x转到Splay根 tr[x].v = y; // 修改权值 pushup(x); // 更新信息 } int main(){ scanf("%d%d", &n, &m); // 读入节点数和操作数 // 读入每个节点的初始权值 for(int i=1; i<=n; i++) scanf("%d", &tr[i].v); int t,x,y; while(m--){ // 处理m个操作 scanf("%d%d%d", &t, &x, &y); if(t == 0) output(x,y); // 操作0：查询路径异或和 else if(t == 1) link(x,y); // 操作1：加边 else if(t == 2) cut(x,y); // 操作2：删边 else change(x,y); // 操作3：修改节点权值 } return 0; }