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 一种路径分解 路径11-2-4-7 路径23 路径35-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 // 步骤1makeroot(4) // 4成为新根树变成 4 \ 2 / \ 1 3 \ 5 \ 6 / 7 // 步骤2access(6) // 打通4到6的路径4-2-1-5-6 // 这条路径成为实链 // 步骤3splay(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 y0; 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) xx和y在同一棵树防止删不同树的节点 //fa(y) xy的父亲是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 i1; in; 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; }