本地源文件：docs/graph__dynamic-tree-divide.md

动态树分治

动态点分治

动态点分治用来解决 带点权/边权修改 的树上路径信息统计问题．

点分树

回顾点分治的计算过程．

对于一个结点 𝑥x 来说，其子树中的简单路径包括两种：经过结点 𝑥x 的，由一条或两条从 𝑥x 出发的路径组成的；和不经过结点 𝑥x 的，即已经包含在其所有儿子结点子树中的路径．

对于一个子树中简单路径的计算，我们选择一个分治中心 𝑟𝑡rt，计算经过该节点的子树中路径的信息，然后对于其每个儿子结点，将删去 𝑟𝑡rt 后该点所在连通块作为一个子树，递归计算．选择的分治中心点可以构成一个树形结构，称为 点分树 ．我们发现，计算点分树中同一层的结点所代表的连通块（即以该结点为分治中心的连通块）的大小总和是 𝑂(𝑛)O(n) 的．这意味着，点分治的时间复杂度是与点分树的深度相关的，若点分树的深度为 ℎh，则点分治的复杂度为 𝑂(𝑛ℎ)O(nh)．

可以证明，当我们每次选择连通块的重心作为分治中心的时候，点分树的深度最小，为 𝑂(log⁡𝑛)O(log⁡n) 的．这样，我们就可以在 𝑂(𝑛log⁡𝑛)O(nlog⁡n) 的时间复杂度内统计树上 𝑂(𝑛2)O(n2) 条路径的信息了．

由于树的形态在动态点分治的过程中不会改变，所以点分树的形态在动态点分治的过程中也不会改变．

下面给出求点分树的参考代码：

---|---

### 实现修改

在查询和修改的时候，我们在点分树上暴力跳父亲修改．由于点分树的深度最多是 𝑂(log⁡𝑛)O(log⁡n)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的，所以这样做复杂度能得到保证．

在动态点分治的过程中，需要一个结点到其点分树上的祖先的距离等其他信息，由于一个点最多有 𝑂(log⁡𝑛)O(log⁡n)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 个祖先，我们可以在计算点分树时额外计算深度 𝑑𝑒𝑝[𝑥]dep[x]![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 或使用 LCA，预处理出这些距离或实现实时查询．**注意** ：一个结点到其点分树上的祖先的距离不一定递增，不能累加！

在动态点分治的过程中，一个结点在其点分树上的祖先结点的信息中可能会被重复计算，这是我们需要消去重复部分的影响．一般的方法是对于一个连通块用两种方式记录：一个是其到分治中心的距离信息，另一个是其到点分树上分治中心父亲的距离信息．这一部分内容将在例题中得到展现．

例题 [「ZJOI2007」捉迷藏](https://www.luogu.com.cn/problem/P2056)

给定一棵有 𝑛n![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 个结点的树，初始时所有结点都是黑色的．你需要实现以下两种操作：

  1. 反转一个结点的颜色（白变黑，黑变白）；
  2. 询问树上两个最远的黑点的距离．

𝑛 ≤105,𝑚 ≤5 ×105n≤105,m≤5×105![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)

求出点分树，对于每个结点 𝑥x![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 维护两个 **可删堆** ．𝑑𝑖𝑠𝑡[𝑥]dist[x]![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 存储结点 𝑥x![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 代表的连通块中的所有黑点到 𝑥x![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的距离信息，𝑐ℎ[𝑥]ch[x]![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 表示结点 𝑥x![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 在点分树上的所有儿子和它自己中的黑点到 𝑥x![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的距离信息，由于本题贪心的求答案方法，且两个来自于同一子树的路径不能成为一条完成的路径，我们只在这个堆中插入其自己的值和其每个子树中的最大值．我们发现，𝑐ℎ[𝑥]ch[x]![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 中最大的两个值（如果没有两个就是所有值）的和就是分治时分支中心为 𝑥x![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 时经过结点 𝑥x![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的最长黑端点路径．我们可以用可删堆 𝑎𝑛𝑠ans![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 存储所有结点的答案，这个堆中的最大值就是我们所求的答案．

我们可以根据上面的定义维护 𝑑𝑖𝑠𝑡[𝑥],𝑐ℎ[𝑥],𝑎𝑛𝑠dist[x],ch[x],ans![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 这些可删堆．当 𝑑𝑖𝑠𝑡[𝑥]dist[x]![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 中的值发生变化时，我们也可以在 𝑂(log⁡𝑛)O(log⁡n)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的时间复杂度内维护 𝑐ℎ[𝑥],𝑎𝑛𝑠ch[x],ans![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．

现在我们来看一下，当我们反转一个点的颜色时，𝑑𝑖𝑠𝑡[𝑥]dist[x]![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 值会发生怎样的改变．当结点原来是黑色时，我们要进行的是删除操作；当结点原来是白色时，我们要进行的是插入操作．

假如我们要反转结点 𝑥x![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的颜色．对于其所有祖先 𝑢u![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)，我们在 𝑑𝑖𝑠𝑡[𝑢]dist[u]![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 中插入或删除 𝑑𝑖𝑠𝑡(𝑥,𝑢)dist(x,u)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)，并同时维护 𝑐ℎ[𝑥],𝑎𝑛𝑠ch[x],ans![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的值．特别的，我们要在 𝑐ℎ[𝑥]ch[x]![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 中插入或删除值 00![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．

参考代码：

---|---

例题 Luogu P6329【模板】点分树 | 震波

给定一棵有 𝑛n 个结点的树，树上每个结点都有一个权值 𝑣[𝑥]v[x]．实现以下两种操作：

询问与结点 𝑥x 距离不超过 𝑦y 的结点权值和；
修改结点 𝑥x 的点权为 𝑦y，即 𝑣[𝑥] =𝑦v[x]=y．

我们用动态开点权值线段树记录距离信息．

类似于上题的思路，对于每个结点，我们维护线段树 𝑑𝑖𝑠𝑡[𝑥]dist[x]，表示分治块 𝑥x 中的所有结点到结点 𝑥x 的距离信息，下标为距离，权值加上点权．线段树 𝑐ℎ[𝑥]ch[x] 表示分治块 𝑥x 中所有结点到结点 𝑥x 在分治树上的父亲结点的距离信息．

在本题中，所有查询和修改都需要在点分树上对所有祖先进行修改．

以查询操作为例，如果我们要查询距离结点 𝑥x 不超过 𝑦y 的结点的权值和，我们要先将答案加上线段树 𝑑𝑖𝑠𝑡[𝑥]dist[x] 中下标从 00 到 𝑦y 的权值和，然后我们遍历 𝑥x 的所有祖先 𝑢u，设其低一级祖先为 𝑣v，令 𝑑 =𝑑𝑖𝑠𝑡(𝑥,𝑢)d=dist(x,u)，如果我们不进入包含 𝑥x 的子树，即以 𝑣v 为根的子树，那么我们要将答案加上线段树 𝑑𝑖𝑠𝑡[𝑢]dist[u] 中下标从 00 到 𝑦 −𝑑y−d 的权值和．由于我们重复计算了以 𝑣v 为根的部分，我们要将答案减去线段树 𝑐ℎ[𝑣]ch[v] 中下标从 00 到 𝑦 −𝑑y−d 的权值和．

在进行修改操作时，我们要同时维护 𝑑𝑖𝑠𝑡[𝑥]dist[x] 和 𝑐ℎ[𝑥]ch[x]．

参考代码：

---|---

* * *

> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/graph/dynamic-tree-divide.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/graph/dynamic-tree-divide.md "edit.link.title")
>  __本页面贡献者：[Ir1d](https://github.com/Ir1d), [StudyingFather](https://github.com/StudyingFather), [H-J-Granger](https://github.com/H-J-Granger), [countercurrent-time](https://github.com/countercurrent-time), [NachtgeistW](https://github.com/NachtgeistW), [Enter-tainer](https://github.com/Enter-tainer), [hsfzLZH1](https://github.com/hsfzLZH1), [sshwy](https://github.com/sshwy), [AngelKitty](https://github.com/AngelKitty), [CCXXXI](https://github.com/CCXXXI), [cjsoft](https://github.com/cjsoft), [diauweb](https://github.com/diauweb), [Early0v0](https://github.com/Early0v0), [ezoixx130](https://github.com/ezoixx130), [GekkaSaori](https://github.com/GekkaSaori), [Henry-ZHR](https://github.com/Henry-ZHR), [Konano](https://github.com/Konano), [LovelyBuggies](https://github.com/LovelyBuggies), [Makkiy](https://github.com/Makkiy), [mgt](mailto:i@margatroid.xyz), [minghu6](https://github.com/minghu6), [ouuan](https://github.com/ouuan), [P-Y-Y](https://github.com/P-Y-Y), [PotassiumWings](https://github.com/PotassiumWings), [SamZhangQingChuan](https://github.com/SamZhangQingChuan), [Suyun514](mailto:suyun514@qq.com), [weiyong1024](https://github.com/weiyong1024), [c-forrest](https://github.com/c-forrest), [GavinZhengOI](https://github.com/GavinZhengOI), [Gesrua](https://github.com/Gesrua), [kenlig](https://github.com/kenlig), [ksyx](https://github.com/ksyx), [kxccc](https://github.com/kxccc), [lychees](https://github.com/lychees), [Menci](https://github.com/Menci), [Peanut-Tang](https://github.com/Peanut-Tang), [SukkaW](https://github.com/SukkaW), [Tiphereth-A](https://github.com/Tiphereth-A), [woshiluo](https://github.com/woshiluo)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用