1. 什么是动态树动态树Dynamic Tree又称 Link-Cut Tree是一种用于维护森林由多棵树组成的集合并支持动态连接与断开操作的高级数据结构。它由 Robert Tarjan 和 Daniel Sleator 提出能够高效地处理树上的路径查询与更新问题。与静态树如普通二叉树、线段树不同动态树允许在算法运行过程中改变树的形态例如将两棵树连接Link起来。将一棵树分割Cut成两棵子树。查询或修改树上某条路径的权值如路径和、最大值等。2. 核心思想与数据结构动态树的核心思想是将一棵树分解为若干条“偏爱路径”Preferred Path并用伸展树Splay Tree来维护每条路径。通过 Splay Tree 的旋转操作可以保证均摊 O(log n) 的时间复杂度。主要操作依赖以下几个概念Access(u)将节点 u 到根节点的路径变为一条偏爱路径并使其成为所在 Splay Tree 的根。MakeRoot(u)将节点 u 设为整棵树的根通过 Access Splay 翻转实现。FindRoot(u)返回节点 u 所在树的根节点。Link(u, v)如果 u 和 v 不在同一棵树中则将 u 所在树的根连接到 v要求 u 是所在树的根。Cut(u, v)如果 u 和 v 之间有边则删除该边将树分成两部分。3. 基础操作实现伪代码以下是用类 C 风格描述的动态树核心操作框架struct Node { Node *ch[2], *fa; int rev; // 翻转标记 // 其他维护信息如权值、子树和等 void pushdown() { /* 下传翻转标记 */ } void pushup() { /* 更新维护信息 */ } bool isroot() { return fa nullptr || (fa-ch[0] ! this fa-ch[1] ! this); } void rotate() { /* Splay 旋转 */ } void splay() { /* 将当前节点伸展到所在 Splay Tree 的根 */ } }; void access(Node *x) { for (Node *y nullptr; x ! nullptr; y x, x x-fa) { x-splay(); x-ch[1] y; x-pushup(); } } void makeroot(Node *x) { access(x); x-splay(); x-rev ^ 1; // 翻转整条路径 } Node* findroot(Node *x) { access(x); x-splay(); while (x-ch[0]) { x x-ch[0]; x-pushdown(); } x-splay(); return x; } void link(Node *x, Node *y) { makeroot(x); if (findroot(y) ! x) { x-fa y; } } void cut(Node *x, Node *y) { makeroot(x); access(y); y-splay(); if (y-ch[0] x x-ch[1] nullptr) { y-ch[0] x-fa nullptr; y-pushup(); } }4. 典型应用场景动态连通性维护森林的连通性支持加边、删边、查询两点是否连通。路径查询查询树上两点间路径的权值和、最大值、最小值等。子树查询需配合 Euler Tour Tree 等扩展查询某棵子树的信息。网络流在 Dinic 等最大流算法中动态维护层次图。图论问题如动态最小生成树Dynamic MST、维护双连通分量等。5. 时间复杂度与注意事项在均摊意义下动态树的基本操作Access、MakeRoot、Link、Cut 等时间复杂度为O(log n)其中 n 为节点数。使用动态树时需要注意正确实现 Splay Tree 的旋转、标记下传与信息上传。确保每次操作前后树的形态合法如 Link 前要求 u 是所在树的根。在维护路径权值时需在 Splay Tree 节点中存储额外信息如 sum、max并在 pushup 中更新。6. 总结动态树是处理动态树形问题的强大工具它将树分解为偏爱路径并用 Splay Tree 维护从而实现了高效的动态连接、断开与路径查询。虽然实现较为复杂但一旦掌握能够解决许多静态数据结构难以处理的动态图论问题。学习动态树建议从理解 Access 操作和 Splay Tree 开始再逐步实现 Link、Cut 等高级操作最后尝试解决一些经典例题如「BZOJ 3282 Tree」、「SPOJ QTREE」等。
1. 什么是动态树动态树Dynamic Tree又称 Link-Cut Tree是一种用于维护森林由多棵树组成的集合并支持动态连接与断开操作的高级数据结构。它由 Robert Tarjan 和 Daniel Sleator 提出能够高效地处理树上的路径查询与更新问题。与静态树如普通二叉树、线段树不同动态树允许在算法运行过程中改变树的形态例如将两棵树连接Link起来。将一棵树分割Cut成两棵子树。查询或修改树上某条路径的权值如路径和、最大值等。2. 核心思想与数据结构动态树的核心思想是将一棵树分解为若干条“偏爱路径”Preferred Path并用伸展树Splay Tree来维护每条路径。通过 Splay Tree 的旋转操作可以保证均摊 O(log n) 的时间复杂度。主要操作依赖以下几个概念Access(u)将节点 u 到根节点的路径变为一条偏爱路径并使其成为所在 Splay Tree 的根。MakeRoot(u)将节点 u 设为整棵树的根通过 Access Splay 翻转实现。FindRoot(u)返回节点 u 所在树的根节点。Link(u, v)如果 u 和 v 不在同一棵树中则将 u 所在树的根连接到 v要求 u 是所在树的根。Cut(u, v)如果 u 和 v 之间有边则删除该边将树分成两部分。3. 基础操作实现伪代码以下是用类 C 风格描述的动态树核心操作框架struct Node { Node *ch[2], *fa; int rev; // 翻转标记 // 其他维护信息如权值、子树和等 void pushdown() { /* 下传翻转标记 */ } void pushup() { /* 更新维护信息 */ } bool isroot() { return fa nullptr || (fa-ch[0] ! this fa-ch[1] ! this); } void rotate() { /* Splay 旋转 */ } void splay() { /* 将当前节点伸展到所在 Splay Tree 的根 */ } }; void access(Node *x) { for (Node *y nullptr; x ! nullptr; y x, x x-fa) { x-splay(); x-ch[1] y; x-pushup(); } } void makeroot(Node *x) { access(x); x-splay(); x-rev ^ 1; // 翻转整条路径 } Node* findroot(Node *x) { access(x); x-splay(); while (x-ch[0]) { x x-ch[0]; x-pushdown(); } x-splay(); return x; } void link(Node *x, Node *y) { makeroot(x); if (findroot(y) ! x) { x-fa y; } } void cut(Node *x, Node *y) { makeroot(x); access(y); y-splay(); if (y-ch[0] x x-ch[1] nullptr) { y-ch[0] x-fa nullptr; y-pushup(); } }4. 典型应用场景动态连通性维护森林的连通性支持加边、删边、查询两点是否连通。路径查询查询树上两点间路径的权值和、最大值、最小值等。子树查询需配合 Euler Tour Tree 等扩展查询某棵子树的信息。网络流在 Dinic 等最大流算法中动态维护层次图。图论问题如动态最小生成树Dynamic MST、维护双连通分量等。5. 时间复杂度与注意事项在均摊意义下动态树的基本操作Access、MakeRoot、Link、Cut 等时间复杂度为O(log n)其中 n 为节点数。使用动态树时需要注意正确实现 Splay Tree 的旋转、标记下传与信息上传。确保每次操作前后树的形态合法如 Link 前要求 u 是所在树的根。在维护路径权值时需在 Splay Tree 节点中存储额外信息如 sum、max并在 pushup 中更新。6. 总结动态树是处理动态树形问题的强大工具它将树分解为偏爱路径并用 Splay Tree 维护从而实现了高效的动态连接、断开与路径查询。虽然实现较为复杂但一旦掌握能够解决许多静态数据结构难以处理的动态图论问题。学习动态树建议从理解 Access 操作和 Splay Tree 开始再逐步实现 Link、Cut 等高级操作最后尝试解决一些经典例题如「BZOJ 3282 Tree」、「SPOJ QTREE」等。
