OI-wiki 动态点分治点分树算法详解带修改树上路径统计问题【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读动态点分治Dynamic Centroid Decomposition又称点分树用于解决带点权/边权修改的树上路径信息统计问题。它通过把原树重构为一棵深度稳定为 $O(\log n)$ 的点分树将原本需要 $O(n)$ 甚至更高的树上路径统计转化为在点分树上暴力跳祖先即可完成的 $O(\log^2 n)$ 级别操作。本文以 OI-wiki 中 动态点分治文档 为主体结合仓库内的 参考代码一捉迷藏、参考代码二震波 与对应 测试数据系统讲解点分树的构建、修改操作的实现技巧、重复贡献消除方法并完整拆解「ZJOI2007 捉迷藏」与「P6329【模板】点分树|震波」两道经典例题。读完本文你将掌握动态点分治的完整套路能够独立解决一类支持单点修改 路径/距离统计的树上问题。点分树把点分治的分治过程固化成树从点分治出发回顾点分治的计算过程。对于一个结点 $x$ 来说其子树中的简单路径包括两种经过结点 $x$ 的由一条或两条从 $x$ 出发的路径组成不经过结点 $x$ 的已经包含在其所有儿子结点子树中的路径。对于一个子树中简单路径的计算我们选择一个分治中心 $rt$计算经过该结点的子树中路径的信息然后对于其每个儿子结点将删去 $rt$ 后该点所在连通块作为一个子树递归计算。选择的分治中心点可以构成一个树形结构称为点分树。可以发现一个关键性质计算点分树中同一层的结点所代表的连通块即以该结点为分治中心的连通块的大小总和是 $O(n)$ 的。这意味着点分治的时间复杂度与点分树的深度相关——若点分树的深度为 $h$则点分治的复杂度为 $O(nh)$。可以证明当我们每次选择连通块的重心作为分治中心时点分树的深度最小为 $O(\log n)$。这样我们就可以在 $O(n\log n)$ 的时间复杂度内统计树上 $O(n^2)$ 条路径的信息。为什么适合动态动态点分治之所以能应对带修改的树上路径统计核心在于一条性质由于树的形态在动态点分治的过程中不会改变所以点分树的形态在动态点分治的过程中也不会改变。也就是说点分树是一次性静态构建的。构建完成后无论原树上的点权/边权如何被修改点分树的父子结构都固定不变。这保证了后续每次修改和查询都只需在深度为 $O(\log n)$ 的点分树上暴力跳祖先从而获得稳定的复杂度保证。这正是点分树常用于解决与树原形态无关的带修改问题的原因参见 tree-divide.md 点分树小节。求点分树的参考代码构建点分树的过程就是反复找重心 → 标记删除 → 递归子树。下面是 OI-wiki 文档中给出的参考实现void calcsiz(int x, int f) { siz[x] 1; maxx[x] 0; for (int j h[x]; j; j nxt[j]) if (p[j] ! f !vis[p[j]]) { calcsiz(p[j], x); siz[x] siz[p[j]]; maxx[x] max(maxx[x], siz[p[j]]); } maxx[x] max(maxx[x], sum - siz[x]); // maxx[x] 表示以 x 为根时的最大子树大小 if (maxx[x] maxx[rt]) rt x; // 这里不能写 保证在第二次 calcsiz 时 rt 不改变 } void pre(int x) { vis[x] true; // 表示在之后的过程中不考虑 x 这个点 for (int j h[x]; j; j nxt[j]) if (!vis[p[j]]) { sum siz[p[j]]; rt 0; maxx[rt] inf; calcsiz(p[j], -1); calcsiz(rt, -1); // 计算两次第二次求出以 rt 为根时的各子树大小 fa[rt] x; pre(rt); // 记录点分树上的父亲 } } int main() { sum n; rt 0; maxx[rt] inf; calcsiz(1, -1); calcsiz(rt, -1); pre(rt); }这段代码有两点实现细节值得注意完整可运行版本见 dynamic-tree-divide_1.cppcalcsiz需要调用两次第一次从任意点出发找出连通块的重心 $rt$第二次以 $rt$ 为根重新计算各子树大小siz供后续递归时确定下一层的连通块大小。更新重心时使用而非代码注释明确说明这里不能写这是为了保证在第二次calcsiz时 $rt$ 不会因为大小相等而改变确保两次计算得到同一个重心。fa[rt] x记录了点分树上的父子关系即当前重心 $rt$ 在点分树上的父亲是上一层分治中心 $x$。在点分树上实现修改与查询暴力跳祖先复杂度保证的根源点分树构建完成后所有修改和查询操作都遵循同一套模式在查询和修改的时候我们在点分树上暴力跳父亲修改。由于点分树的深度最多是 $O(\log n)$ 的所以这样做复杂度能得到保证。即对结点 $x$ 的一次操作需要遍历 $x$ 在点分树上的所有祖先包括它自己并在每个祖先维护的信息结构上进行更新或统计。因为每个点最多有 $O(\log n)$ 个祖先总复杂度为 $O(\log n)$ 乘上每次单点操作的代价。距离信息的预处理在动态点分治的过程中我们需要一个结点到其点分树上的祖先的距离等信息。由于一个点最多有 $O(\log n)$ 个祖先我们可以在计算点分树时额外计算深度dep[x]或使用 LCA预处理出这些距离或实现实时查询。仓库两份参考代码均采用LCA 二维数组缓存的方式。以 dynamic-tree-divide_1.cpp 为例构建完成后统一执行for (int i 1; i n; i) for (int j i; j; j fa[j]) d[i][dep[i] - dep[j]] lca.dist(i, j);其中dep[i]是点分树上的深度d[i][k]缓存了 $i$ 到其点分树上第 $k$ 级祖先的原树距离。之所以这样设计是因为注意一个结点到其点分树上的祖先的距离不一定递增不能累加也就是说$dist(x, u_1) dist(u_1, u_2)$ 并不一定等于 $dist(x, u_2)$——点分树上的祖先关系与原树上的路径并不对应。因此不能通过点分树深度差累加来求距离必须借助原树的 LCA 实时计算或预先缓存。重复贡献的消除双信息记录法在动态点分治的过程中一个结点在其点分树上的祖先结点的信息中可能会被重复计算这是我们需要消去重复部分的影响。一般的方法是对于一个连通块用两种方式记录一个结点到其分治中心的距离信息一个结点到其点分树上分治中心父亲的距离信息。这一一正一负的双结构设计是整个动态点分治套路的核心统计祖先 $u$ 的覆盖范围时先加分治块 $u$ 内所有点到 $u$ 的信息再减去其中来自包含 $x$ 的那个儿子子树的信息从而保证每个点恰好被计算一次。下面两道例题将具体展现这两种记录方式的具体形态可删堆 / 权值线段树。例题一[ZJOI2007] 捉迷藏可删堆维护最长黑点距离题目与思路给定一棵有 $n$ 个结点的树初始时所有结点都是黑色的。你需要实现以下两种操作反转一个结点的颜色白变黑黑变白询问树上两个最远的黑点的距离。数据范围$n\le 10^5, m\le 5\times 10^5$本题是动态点分治的入门经典。做法求出点分树对于每个结点 $x$ 维护两个可删堆dist[x]存储结点 $x$ 代表的连通块中所有黑点到 $x$ 的距离信息ch[x]表示结点 $x$ 在点分树上的所有儿子和它自己中的黑点到 $x$ 的距离信息。由于贪心的求答案方法要求两条路径不能来自同一个子树来自同一子树的路径不能成为一条完整路径我们只在这个堆中插入其自己的值和其每个子树中的最大值。可以发现$ch[x]$ 中最大的两个值如果没有两个就是所有值的和就是分治中心为 $x$ 时经过结点 $x$ 的最长黑端点路径。再用一个可删堆ans存储所有结点的答案ans中的最大值就是所求答案。可删堆的实现由于需要支持删除历史值普通优先队列不够用。仓库代码用一个struct heap封装了双堆技巧堆 $A$ 减去堆 $B$见 dynamic-tree-divide_1.cppstruct heap { priority_queueint A, B; // heapA-B void insert(int x) { A.push(x); } void erase(int x) { B.push(x); } int top() { while (!B.empty() A.top() B.top()) A.pop(), B.pop(); return A.top(); } void pop() { while (!B.empty() A.top() B.top()) A.pop(), B.pop(); A.pop(); } int top2() { int t top(), ret; pop(); ret top(); A.push(t); return ret; } int size() { return A.size() - B.size(); } } dist[MAXN], ch[MAXN], ans;insert/erase分别把元素压入 $A$ 堆与 $B$ 堆真正有效的集合是 $A - B$top/pop在取顶前先把 $A$ 堆顶中已被 $B$ 标记删除的元素同步弹出惰性删除top2通过取出最大 → 再取次大 → 放回最大实现求堆中最大的两个值之和所需的第二最大值。预处理阶段的信息收集构建点分树时同时用一次 DFS 收集距离信息dynamic-tree-divide_1.cppvoid dfs(int x, int f, int d, heap y) { y.insert(d); for (int j h[x]; j; j nxt[j]) if (p[j] ! f !vis[p[j]]) dfs(p[j], x, d 1, y); }对每个分治中心 $rt$把其儿子连通块内所有点到 $rt$ 的距离插入dist[rt]并把该连通块的最大距离dist[rt].top()插入父亲的ch[fa[rt]]最后在ch[x]中插入自身的距离 $0$并根据ch[x]的前两大值初始化ans。注意这里的距离是原树上的距离由于边权均为 $1$用 DFS 层数即可若存在边权则应改用 LCA 计算。修改操作翻转一个点的颜色当dist[x]中的值发生变化时我们可以在 $O(\log n)$ 的时间复杂度内维护ch[x]与ans。翻转结点 $x$ 的颜色时对于其所有祖先 $u$我们在dist[u]中插入或删除 $dist(x,u)$并同时维护ch、ans的值特别地要在ch[x]中插入或删除值 $0$自身贡献。结点原来是黑色时执行的是删除操作结点原来是白色时执行的是插入操作。以黑变白删除分支为例dynamic-tree-divide_1.cppif (!col[x]) { if (ch[x].size() 2) ans.erase(ch[x].top() ch[x].top2()); ch[x].erase(0); if (ch[x].size() 2) ans.insert(ch[x].top() ch[x].top2()); for (int i x; fa[i]; i fa[i]) { if (ch[fa[i]].size() 2) ans.erase(ch[fa[i]].top() ch[fa[i]].top2()); ch[fa[i]].erase(dist[i].top()); dist[i].erase(d[x][dep[x] - dep[fa[i]]]); if (dist[i].size()) ch[fa[i]].insert(dist[i].top()); if (ch[fa[i]].size() 2) ans.insert(ch[fa[i]].top() ch[fa[i]].top2()); } cnt--; }每个祖先的操作套路都是固定的三步从ans中删除该祖先旧的答案ch[fa[i]]前两大值之和在该祖先的信息结构上更新距离dist[i]增删 $d[x][\cdot]$ch[fa[i]]随之调整把新的前两大值之和重新插入ans。查询操作则直接输出ans.top()若当前没有黑点cnt 0输出-1。测试数据验证仓库提供了本题的测试数据 dynamic-tree-divide_1.in 与 dynamic-tree-divide_1.ans一棵 8 个结点的树初始全黑时查询得 4翻转点 1变白后查询得 3翻转点 2变白后查询得 3再翻转点 1变黑后查询得 4。整个流程正好覆盖了插入、删除、再次插入三种状态切换验证了双堆维护的正确性。例题二Luogu P6329【模板】点分树 | 震波权值线段树统计距离题目与数据结构设计给定一棵有 $n$ 个结点的树树上每个结点都有一个权值 $v[x]$。实现以下两种操作询问与结点 $x$ 距离不超过 $y$ 的结点权值和修改结点 $x$ 的点权为 $y$即 $v[x]y$。本题是点分树 动态开点权值线段树的模板题也是双信息记录法最标准的呈现。我们用动态开点权值线段树记录距离信息线段树dist[x]分治块 $x$ 中所有结点到结点 $x$ 的距离信息下标为距离权值加上点权线段树ch[x]分治块 $x$ 中所有结点到结点 $x$ 在分治树上的父亲结点的距离信息。线段树的实现动态开点、单点加、区间求和见 dynamic-tree-divide_2.cppstruct Segtree { int cnt, rt[MAXN], sum[ddd], lc[ddd], rc[ddd]; void update(int o, int l, int r, int x, int v) { if (!o) o cnt; if (l r) { sum[o] v; return; } int mid (l r) 1; if (x mid) update(lc[o], l, mid, x, v); else update(rc[o], mid 1, r, x, v); sum[o] sum[lc[o]] sum[rc[o]]; } int query(int o, int l, int r, int ql, int qr) { if (!o || r ql || l qr) return 0; if (ql l r qr) return sum[o]; int mid (l r) 1; return query(lc[o], l, mid, ql, qr) query(rc[o], mid 1, r, ql, qr); } } dist, ch;预处理两遍 DFS 分别填充 dist 与 ch构建点分树时对每个分治中心 $y$ 做两遍 DFSdynamic-tree-divide_2.cppdfs2把分治块内所有点到 $y$ 的距离写入dist[y]距离从 $0$ 开始dfs1把每个儿子连通块内的点到 $y$ 的距离写入ch[rt]其中 $rt$ 是该连通块新的分治中心即 $y$ 在点分树上的儿子距离从 $1$ 开始。void dfs1(int x, int fa, int y, int d) { ch.update(ch.rt[y], 0, n, d, val[x]); for (int j h[x]; j; j nxt[j]) if (p[j] ! fa !vis[p[j]]) dfs1(p[j], x, y, d 1); } void dfs2(int x, int fa, int y, int d) { dist.update(dist.rt[y], 0, n, d, val[x]); for (int j h[x]; j; j nxt[j]) if (p[j] ! fa !vis[p[j]]) dfs2(p[j], x, y, d 1); }注意ch记录的正是到点分树上父亲的距离这与dist记录到分治中心自己的距离形成互补——二者之差恰好消除了重复贡献。查询操作容斥式累加在本题中所有查询和修改都需要在点分树上对所有祖先进行修改。查询距离结点 $x$ 不超过 $y$ 的结点权值和时dynamic-tree-divide_2.cpplstans dist.query(dist.rt[x], 0, n, 0, y); int nww 0; for (int i x; fa[i]; i fa[i]) { nww d[x][dep[x] - dep[fa[i]]]; // lca.dist(x,fa[i]); lstans dist.query(dist.rt[fa[i]], 0, n, 0, y - nww); lstans - ch.query(ch.rt[i], 0, n, 0, y - nww); }算法的容斥逻辑如下先加自己答案加上线段树dist[x]中下标从 $0$ 到 $y$ 的权值和再遍历 $x$ 的所有祖先 $u$设其低一级祖先为 $v$即从 $x$ 向上跳的上一级令 $d dist(x,u)$。如果我们不进入包含 $x$ 的子树即以 $v$ 为根的子树那么要将答案加上线段树dist[u]中下标从 $0$ 到 $y-d$ 的权值和减去重复部分由于我们重复计算了以 $v$ 为根的部分要将答案减去线段树ch[v]中下标从 $0$ 到 $y-d$ 的权值和。这里 $d$ 通过预处理的d[x][dep[x] - dep[fa[i]]]直接取出等价于lca.dist(x, fa[i])避免了重复计算。修改操作同步更新 dist 与 ch修改结点 $x$ 的点权为 $y$ 时dynamic-tree-divide_2.cpp需要对点分树上所有祖先的线段树做差值修改int nww 0; dist.update(dist.rt[x], 0, n, 0, y - val[x]); for (int i x; fa[i]; i fa[i]) { nww d[x][dep[x] - dep[fa[i]]]; // lca.dist(x,fa[i]); dist.update(dist.rt[fa[i]], 0, n, nww, y - val[x]); ch.update(ch.rt[i], 0, n, nww, y - val[x]); } val[x] y;即对每个祖先 $u$在dist[u]的距离 $dist(x,u)$ 位置上增加差值 $\Delta y - val[x]$同时在ch[u]记录到点分树父亲的距离的对应位置上增加同样的差值。一次修改的总代价为 $O(\log n \cdot \log n)$点分树深度 $\times$ 线段树操作代价。强制在线与测试数据本题输入输出均做了异或加密x ^ lstans; y ^ lstans;要求算法强制在线处理这进一步说明了点分树一次构建、多次跳祖先结构的必要性——它天然支持在线修改与查询不需要任何离线重排。仓库测试数据 dynamic-tree-divide_2.in 中8 个结点的权值为 $1,10,100,\dots,10^7$一次查询0 3 1询问与结点 3 距离不超过 1 的权值和结点 3 自身100、结点 11、结点 6/7/8$10^510^610^7$由于强制在线解密后答案为 11100101与 答案文件 完全吻合可用来验证实现正确性。复杂度分析与适用场景总结复杂度阶段时间复杂度空间复杂度构建点分树$O(n \log n)$$O(n \log n)$缓存距离数组单次修改捉迷藏$O(\log^2 n)$可删堆 $O(n \log n)$单次查询捉迷藏$O(1)$取堆顶—单次修改震波$O(\log^2 n)$动态开点线段树 $O(n \log n)$单次查询震波$O(\log^2 n)$—点分树深度的 $O(\log n)$ 保证来自每次选择重心的构建策略而每次修改/查询最多访问 $O(\log n)$ 个祖先每个祖先上的堆/线段树操作再乘 $O(\log n)$总代价为 $O(\log^2 n)$。套路总结与适用前提从两道例题可以看出动态点分治的通用解题框架构建点分树每次取重心标记删除递归子树记录fa预处理距离用 LCA或 DFS 层数缓存每个点与其点分树祖先的原树距离注意点分树上的距离不可累加双结构记录为每个点维护到自身与到点分树父亲两份信息查询/修改时加dist减ch消除重复贡献数据结构选型根据统计需求选择可删堆维护最大/次大值或动态开点权值线段树维护距离区间和等。适用前提题目所修改的内容点权/边权与原树形态无关即修改操作只影响权值、不改变树的形态——这正是点分树一次构建、永久使用的前提。若修改会改变树的结构点分树将不再适用需要另寻动态树结构。读者可结合 tree-divide.md 中的静态点分治内容含 重心 的定义与性质打牢基础再对照本文两份完整参考代码 dynamic-tree-divide_1.cpp 与 dynamic-tree-divide_2.cpp 以及对应测试数据逐步理解即可将动态点分治这一套路熟练运用于各类带修改树上路径统计问题。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
OI-wiki 动态点分治点分树算法详解带修改树上路径统计问题【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读动态点分治Dynamic Centroid Decomposition又称点分树用于解决带点权/边权修改的树上路径信息统计问题。它通过把原树重构为一棵深度稳定为 $O(\log n)$ 的点分树将原本需要 $O(n)$ 甚至更高的树上路径统计转化为在点分树上暴力跳祖先即可完成的 $O(\log^2 n)$ 级别操作。本文以 OI-wiki 中 动态点分治文档 为主体结合仓库内的 参考代码一捉迷藏、参考代码二震波 与对应 测试数据系统讲解点分树的构建、修改操作的实现技巧、重复贡献消除方法并完整拆解「ZJOI2007 捉迷藏」与「P6329【模板】点分树|震波」两道经典例题。读完本文你将掌握动态点分治的完整套路能够独立解决一类支持单点修改 路径/距离统计的树上问题。点分树把点分治的分治过程固化成树从点分治出发回顾点分治的计算过程。对于一个结点 $x$ 来说其子树中的简单路径包括两种经过结点 $x$ 的由一条或两条从 $x$ 出发的路径组成不经过结点 $x$ 的已经包含在其所有儿子结点子树中的路径。对于一个子树中简单路径的计算我们选择一个分治中心 $rt$计算经过该结点的子树中路径的信息然后对于其每个儿子结点将删去 $rt$ 后该点所在连通块作为一个子树递归计算。选择的分治中心点可以构成一个树形结构称为点分树。可以发现一个关键性质计算点分树中同一层的结点所代表的连通块即以该结点为分治中心的连通块的大小总和是 $O(n)$ 的。这意味着点分治的时间复杂度与点分树的深度相关——若点分树的深度为 $h$则点分治的复杂度为 $O(nh)$。可以证明当我们每次选择连通块的重心作为分治中心时点分树的深度最小为 $O(\log n)$。这样我们就可以在 $O(n\log n)$ 的时间复杂度内统计树上 $O(n^2)$ 条路径的信息。为什么适合动态动态点分治之所以能应对带修改的树上路径统计核心在于一条性质由于树的形态在动态点分治的过程中不会改变所以点分树的形态在动态点分治的过程中也不会改变。也就是说点分树是一次性静态构建的。构建完成后无论原树上的点权/边权如何被修改点分树的父子结构都固定不变。这保证了后续每次修改和查询都只需在深度为 $O(\log n)$ 的点分树上暴力跳祖先从而获得稳定的复杂度保证。这正是点分树常用于解决与树原形态无关的带修改问题的原因参见 tree-divide.md 点分树小节。求点分树的参考代码构建点分树的过程就是反复找重心 → 标记删除 → 递归子树。下面是 OI-wiki 文档中给出的参考实现void calcsiz(int x, int f) { siz[x] 1; maxx[x] 0; for (int j h[x]; j; j nxt[j]) if (p[j] ! f !vis[p[j]]) { calcsiz(p[j], x); siz[x] siz[p[j]]; maxx[x] max(maxx[x], siz[p[j]]); } maxx[x] max(maxx[x], sum - siz[x]); // maxx[x] 表示以 x 为根时的最大子树大小 if (maxx[x] maxx[rt]) rt x; // 这里不能写 保证在第二次 calcsiz 时 rt 不改变 } void pre(int x) { vis[x] true; // 表示在之后的过程中不考虑 x 这个点 for (int j h[x]; j; j nxt[j]) if (!vis[p[j]]) { sum siz[p[j]]; rt 0; maxx[rt] inf; calcsiz(p[j], -1); calcsiz(rt, -1); // 计算两次第二次求出以 rt 为根时的各子树大小 fa[rt] x; pre(rt); // 记录点分树上的父亲 } } int main() { sum n; rt 0; maxx[rt] inf; calcsiz(1, -1); calcsiz(rt, -1); pre(rt); }这段代码有两点实现细节值得注意完整可运行版本见 dynamic-tree-divide_1.cppcalcsiz需要调用两次第一次从任意点出发找出连通块的重心 $rt$第二次以 $rt$ 为根重新计算各子树大小siz供后续递归时确定下一层的连通块大小。更新重心时使用而非代码注释明确说明这里不能写这是为了保证在第二次calcsiz时 $rt$ 不会因为大小相等而改变确保两次计算得到同一个重心。fa[rt] x记录了点分树上的父子关系即当前重心 $rt$ 在点分树上的父亲是上一层分治中心 $x$。在点分树上实现修改与查询暴力跳祖先复杂度保证的根源点分树构建完成后所有修改和查询操作都遵循同一套模式在查询和修改的时候我们在点分树上暴力跳父亲修改。由于点分树的深度最多是 $O(\log n)$ 的所以这样做复杂度能得到保证。即对结点 $x$ 的一次操作需要遍历 $x$ 在点分树上的所有祖先包括它自己并在每个祖先维护的信息结构上进行更新或统计。因为每个点最多有 $O(\log n)$ 个祖先总复杂度为 $O(\log n)$ 乘上每次单点操作的代价。距离信息的预处理在动态点分治的过程中我们需要一个结点到其点分树上的祖先的距离等信息。由于一个点最多有 $O(\log n)$ 个祖先我们可以在计算点分树时额外计算深度dep[x]或使用 LCA预处理出这些距离或实现实时查询。仓库两份参考代码均采用LCA 二维数组缓存的方式。以 dynamic-tree-divide_1.cpp 为例构建完成后统一执行for (int i 1; i n; i) for (int j i; j; j fa[j]) d[i][dep[i] - dep[j]] lca.dist(i, j);其中dep[i]是点分树上的深度d[i][k]缓存了 $i$ 到其点分树上第 $k$ 级祖先的原树距离。之所以这样设计是因为注意一个结点到其点分树上的祖先的距离不一定递增不能累加也就是说$dist(x, u_1) dist(u_1, u_2)$ 并不一定等于 $dist(x, u_2)$——点分树上的祖先关系与原树上的路径并不对应。因此不能通过点分树深度差累加来求距离必须借助原树的 LCA 实时计算或预先缓存。重复贡献的消除双信息记录法在动态点分治的过程中一个结点在其点分树上的祖先结点的信息中可能会被重复计算这是我们需要消去重复部分的影响。一般的方法是对于一个连通块用两种方式记录一个结点到其分治中心的距离信息一个结点到其点分树上分治中心父亲的距离信息。这一一正一负的双结构设计是整个动态点分治套路的核心统计祖先 $u$ 的覆盖范围时先加分治块 $u$ 内所有点到 $u$ 的信息再减去其中来自包含 $x$ 的那个儿子子树的信息从而保证每个点恰好被计算一次。下面两道例题将具体展现这两种记录方式的具体形态可删堆 / 权值线段树。例题一[ZJOI2007] 捉迷藏可删堆维护最长黑点距离题目与思路给定一棵有 $n$ 个结点的树初始时所有结点都是黑色的。你需要实现以下两种操作反转一个结点的颜色白变黑黑变白询问树上两个最远的黑点的距离。数据范围$n\le 10^5, m\le 5\times 10^5$本题是动态点分治的入门经典。做法求出点分树对于每个结点 $x$ 维护两个可删堆dist[x]存储结点 $x$ 代表的连通块中所有黑点到 $x$ 的距离信息ch[x]表示结点 $x$ 在点分树上的所有儿子和它自己中的黑点到 $x$ 的距离信息。由于贪心的求答案方法要求两条路径不能来自同一个子树来自同一子树的路径不能成为一条完整路径我们只在这个堆中插入其自己的值和其每个子树中的最大值。可以发现$ch[x]$ 中最大的两个值如果没有两个就是所有值的和就是分治中心为 $x$ 时经过结点 $x$ 的最长黑端点路径。再用一个可删堆ans存储所有结点的答案ans中的最大值就是所求答案。可删堆的实现由于需要支持删除历史值普通优先队列不够用。仓库代码用一个struct heap封装了双堆技巧堆 $A$ 减去堆 $B$见 dynamic-tree-divide_1.cppstruct heap { priority_queueint A, B; // heapA-B void insert(int x) { A.push(x); } void erase(int x) { B.push(x); } int top() { while (!B.empty() A.top() B.top()) A.pop(), B.pop(); return A.top(); } void pop() { while (!B.empty() A.top() B.top()) A.pop(), B.pop(); A.pop(); } int top2() { int t top(), ret; pop(); ret top(); A.push(t); return ret; } int size() { return A.size() - B.size(); } } dist[MAXN], ch[MAXN], ans;insert/erase分别把元素压入 $A$ 堆与 $B$ 堆真正有效的集合是 $A - B$top/pop在取顶前先把 $A$ 堆顶中已被 $B$ 标记删除的元素同步弹出惰性删除top2通过取出最大 → 再取次大 → 放回最大实现求堆中最大的两个值之和所需的第二最大值。预处理阶段的信息收集构建点分树时同时用一次 DFS 收集距离信息dynamic-tree-divide_1.cppvoid dfs(int x, int f, int d, heap y) { y.insert(d); for (int j h[x]; j; j nxt[j]) if (p[j] ! f !vis[p[j]]) dfs(p[j], x, d 1, y); }对每个分治中心 $rt$把其儿子连通块内所有点到 $rt$ 的距离插入dist[rt]并把该连通块的最大距离dist[rt].top()插入父亲的ch[fa[rt]]最后在ch[x]中插入自身的距离 $0$并根据ch[x]的前两大值初始化ans。注意这里的距离是原树上的距离由于边权均为 $1$用 DFS 层数即可若存在边权则应改用 LCA 计算。修改操作翻转一个点的颜色当dist[x]中的值发生变化时我们可以在 $O(\log n)$ 的时间复杂度内维护ch[x]与ans。翻转结点 $x$ 的颜色时对于其所有祖先 $u$我们在dist[u]中插入或删除 $dist(x,u)$并同时维护ch、ans的值特别地要在ch[x]中插入或删除值 $0$自身贡献。结点原来是黑色时执行的是删除操作结点原来是白色时执行的是插入操作。以黑变白删除分支为例dynamic-tree-divide_1.cppif (!col[x]) { if (ch[x].size() 2) ans.erase(ch[x].top() ch[x].top2()); ch[x].erase(0); if (ch[x].size() 2) ans.insert(ch[x].top() ch[x].top2()); for (int i x; fa[i]; i fa[i]) { if (ch[fa[i]].size() 2) ans.erase(ch[fa[i]].top() ch[fa[i]].top2()); ch[fa[i]].erase(dist[i].top()); dist[i].erase(d[x][dep[x] - dep[fa[i]]]); if (dist[i].size()) ch[fa[i]].insert(dist[i].top()); if (ch[fa[i]].size() 2) ans.insert(ch[fa[i]].top() ch[fa[i]].top2()); } cnt--; }每个祖先的操作套路都是固定的三步从ans中删除该祖先旧的答案ch[fa[i]]前两大值之和在该祖先的信息结构上更新距离dist[i]增删 $d[x][\cdot]$ch[fa[i]]随之调整把新的前两大值之和重新插入ans。查询操作则直接输出ans.top()若当前没有黑点cnt 0输出-1。测试数据验证仓库提供了本题的测试数据 dynamic-tree-divide_1.in 与 dynamic-tree-divide_1.ans一棵 8 个结点的树初始全黑时查询得 4翻转点 1变白后查询得 3翻转点 2变白后查询得 3再翻转点 1变黑后查询得 4。整个流程正好覆盖了插入、删除、再次插入三种状态切换验证了双堆维护的正确性。例题二Luogu P6329【模板】点分树 | 震波权值线段树统计距离题目与数据结构设计给定一棵有 $n$ 个结点的树树上每个结点都有一个权值 $v[x]$。实现以下两种操作询问与结点 $x$ 距离不超过 $y$ 的结点权值和修改结点 $x$ 的点权为 $y$即 $v[x]y$。本题是点分树 动态开点权值线段树的模板题也是双信息记录法最标准的呈现。我们用动态开点权值线段树记录距离信息线段树dist[x]分治块 $x$ 中所有结点到结点 $x$ 的距离信息下标为距离权值加上点权线段树ch[x]分治块 $x$ 中所有结点到结点 $x$ 在分治树上的父亲结点的距离信息。线段树的实现动态开点、单点加、区间求和见 dynamic-tree-divide_2.cppstruct Segtree { int cnt, rt[MAXN], sum[ddd], lc[ddd], rc[ddd]; void update(int o, int l, int r, int x, int v) { if (!o) o cnt; if (l r) { sum[o] v; return; } int mid (l r) 1; if (x mid) update(lc[o], l, mid, x, v); else update(rc[o], mid 1, r, x, v); sum[o] sum[lc[o]] sum[rc[o]]; } int query(int o, int l, int r, int ql, int qr) { if (!o || r ql || l qr) return 0; if (ql l r qr) return sum[o]; int mid (l r) 1; return query(lc[o], l, mid, ql, qr) query(rc[o], mid 1, r, ql, qr); } } dist, ch;预处理两遍 DFS 分别填充 dist 与 ch构建点分树时对每个分治中心 $y$ 做两遍 DFSdynamic-tree-divide_2.cppdfs2把分治块内所有点到 $y$ 的距离写入dist[y]距离从 $0$ 开始dfs1把每个儿子连通块内的点到 $y$ 的距离写入ch[rt]其中 $rt$ 是该连通块新的分治中心即 $y$ 在点分树上的儿子距离从 $1$ 开始。void dfs1(int x, int fa, int y, int d) { ch.update(ch.rt[y], 0, n, d, val[x]); for (int j h[x]; j; j nxt[j]) if (p[j] ! fa !vis[p[j]]) dfs1(p[j], x, y, d 1); } void dfs2(int x, int fa, int y, int d) { dist.update(dist.rt[y], 0, n, d, val[x]); for (int j h[x]; j; j nxt[j]) if (p[j] ! fa !vis[p[j]]) dfs2(p[j], x, y, d 1); }注意ch记录的正是到点分树上父亲的距离这与dist记录到分治中心自己的距离形成互补——二者之差恰好消除了重复贡献。查询操作容斥式累加在本题中所有查询和修改都需要在点分树上对所有祖先进行修改。查询距离结点 $x$ 不超过 $y$ 的结点权值和时dynamic-tree-divide_2.cpplstans dist.query(dist.rt[x], 0, n, 0, y); int nww 0; for (int i x; fa[i]; i fa[i]) { nww d[x][dep[x] - dep[fa[i]]]; // lca.dist(x,fa[i]); lstans dist.query(dist.rt[fa[i]], 0, n, 0, y - nww); lstans - ch.query(ch.rt[i], 0, n, 0, y - nww); }算法的容斥逻辑如下先加自己答案加上线段树dist[x]中下标从 $0$ 到 $y$ 的权值和再遍历 $x$ 的所有祖先 $u$设其低一级祖先为 $v$即从 $x$ 向上跳的上一级令 $d dist(x,u)$。如果我们不进入包含 $x$ 的子树即以 $v$ 为根的子树那么要将答案加上线段树dist[u]中下标从 $0$ 到 $y-d$ 的权值和减去重复部分由于我们重复计算了以 $v$ 为根的部分要将答案减去线段树ch[v]中下标从 $0$ 到 $y-d$ 的权值和。这里 $d$ 通过预处理的d[x][dep[x] - dep[fa[i]]]直接取出等价于lca.dist(x, fa[i])避免了重复计算。修改操作同步更新 dist 与 ch修改结点 $x$ 的点权为 $y$ 时dynamic-tree-divide_2.cpp需要对点分树上所有祖先的线段树做差值修改int nww 0; dist.update(dist.rt[x], 0, n, 0, y - val[x]); for (int i x; fa[i]; i fa[i]) { nww d[x][dep[x] - dep[fa[i]]]; // lca.dist(x,fa[i]); dist.update(dist.rt[fa[i]], 0, n, nww, y - val[x]); ch.update(ch.rt[i], 0, n, nww, y - val[x]); } val[x] y;即对每个祖先 $u$在dist[u]的距离 $dist(x,u)$ 位置上增加差值 $\Delta y - val[x]$同时在ch[u]记录到点分树父亲的距离的对应位置上增加同样的差值。一次修改的总代价为 $O(\log n \cdot \log n)$点分树深度 $\times$ 线段树操作代价。强制在线与测试数据本题输入输出均做了异或加密x ^ lstans; y ^ lstans;要求算法强制在线处理这进一步说明了点分树一次构建、多次跳祖先结构的必要性——它天然支持在线修改与查询不需要任何离线重排。仓库测试数据 dynamic-tree-divide_2.in 中8 个结点的权值为 $1,10,100,\dots,10^7$一次查询0 3 1询问与结点 3 距离不超过 1 的权值和结点 3 自身100、结点 11、结点 6/7/8$10^510^610^7$由于强制在线解密后答案为 11100101与 答案文件 完全吻合可用来验证实现正确性。复杂度分析与适用场景总结复杂度阶段时间复杂度空间复杂度构建点分树$O(n \log n)$$O(n \log n)$缓存距离数组单次修改捉迷藏$O(\log^2 n)$可删堆 $O(n \log n)$单次查询捉迷藏$O(1)$取堆顶—单次修改震波$O(\log^2 n)$动态开点线段树 $O(n \log n)$单次查询震波$O(\log^2 n)$—点分树深度的 $O(\log n)$ 保证来自每次选择重心的构建策略而每次修改/查询最多访问 $O(\log n)$ 个祖先每个祖先上的堆/线段树操作再乘 $O(\log n)$总代价为 $O(\log^2 n)$。套路总结与适用前提从两道例题可以看出动态点分治的通用解题框架构建点分树每次取重心标记删除递归子树记录fa预处理距离用 LCA或 DFS 层数缓存每个点与其点分树祖先的原树距离注意点分树上的距离不可累加双结构记录为每个点维护到自身与到点分树父亲两份信息查询/修改时加dist减ch消除重复贡献数据结构选型根据统计需求选择可删堆维护最大/次大值或动态开点权值线段树维护距离区间和等。适用前提题目所修改的内容点权/边权与原树形态无关即修改操作只影响权值、不改变树的形态——这正是点分树一次构建、永久使用的前提。若修改会改变树的结构点分树将不再适用需要另寻动态树结构。读者可结合 tree-divide.md 中的静态点分治内容含 重心 的定义与性质打牢基础再对照本文两份完整参考代码 dynamic-tree-divide_1.cpp 与 dynamic-tree-divide_2.cpp 以及对应测试数据逐步理解即可将动态点分治这一套路熟练运用于各类带修改树上路径统计问题。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
