树分治小记

最近你可能在本`Blog`看到许多这样的小记,这完全属于省选之前的游击战术,内容不保证严谨,也不保证大多数人能看懂。 如果省选过后有时间我会来仔细更新并且把这些文字去掉的。 可能你会发现没有代码,这是因为我懒得贴,~~而不是在口胡或者咕咕咕~~,等我有空了会回来补的。 少数题目可能没有评测之处,这我也无能为力。 ------------ 内容比较杂,大概有: - 点分治 - 一类按重心移动的(最优化)判定问题 - 边分治 (+边分树合并) - (动态)链分治 (长链剖分 / `dsu on tree` / 全局平衡二叉树) - 点/边分树(建模) - 动态 · 树分治 **有些**(带记录标记的)链接会直接拉到博客中的其他文章(更丰富的)讲解,并不是一句话题解,请留意。 # 点分治 用于解决一类树上路径问题。 **核心思想** : 每次钦定一个点,只统计经过该点的路径。然后各个子树之间便不再有贡献,可以分治。 在树上,只需要选取重心作为分治中心,则可以保证各个子任务的规模都不超过原问题的一半。分治的深度是严格$O(\log_2n)$的。 - 怎么找重心 : 求出每个点的**最大子树大小**,包括朝向根的一部分,可以使用整个联通块的大小来减去本子树大小来计算。 然后取个最大子树大小最小的点即可。 然后,就变成了只处理过根的路径。一般来讲考虑“深度”,分上下讨论就可以了。 - **例题** [P4149 [IOI2011]Race](https://www.luogu.com.cn/problem/P4149) 以当前分治中心为根,经过根的路径的长度可以转化为两个端点的深度。 我们要拼合出恰好为$k$的路径,由于$k$较小,可以直接开桶维护。 主要的难点在于,路径不能自交,也就是说,两个端点必须来自不同子树。 解决的方法类似树形`DP`,先查询完某棵子树,再将其加入桶中(或其他数据结构)。这样就能保证只有来自不同子树的无序对才有贡献。 可以每次枚举修改来清空桶。 子问题大小总和是$O(n\log n)$的,总复杂度与之相同。 [提交记录](https://www.luogu.com.cn/record/33188080) - [P4178 Tree](https://www.luogu.com.cn/problem/P4178) 观察到$k$仍然很小,使用树状数组维护前缀和即可,复杂度是$O(n\log^2n)$。 - [P5351 Ruri Loves Maschera](https://www.luogu.com.cn/problem/P5351) 选取分治中心之后,令$mx[u]$为$u$到根的边权$\max$。 一条路径$(u,v)$的贡献即为$\max(mx[u],mx[v])$。 这里我们略施小计,把有序的路径钦定为在$mx$值较大的一段贡献。注意答案最后乘个$2$。 现在要计算总贡献。分“是最大值”和“不是最大值”讨论即可。 对于半截路径$mx[u]$,只需要考虑$mx$不超过自己的路径。 贡献为 : 不超过$mx[u]$的路径数$\times mx[u]$。别漏了分治中心本身。 这里还需要受到边的条数的限制,就变成了一个二维偏序问题。 但二维偏序是静态的,我们无法像前文那样依次加入各个子树。 注意到,求和类问题可以支持减去贡献,我们在每个子树内单独跑一次把贡献减去即可。 复杂度$O(n\log^2n)$。[评测记录](https://www.luogu.com.cn/record/33190803) - [CF293E Close Vertices](https://www.luogu.com.cn/problem/CF293E) 相信做过上一题之后能看出来是个裸的点分治+二维偏序。复杂度$O(n\log^2n)$。 [评测记录](https://www.luogu.com.cn/record/33220024) - [P3060 [USACO12NOV]平衡树Balanced Trees](https://www.luogu.org/problem/P3060) 从重心计算若干个向上和向下的括号路径。 对于向上的路径,括号对消之后一定得到若干个 `(` 。若遇见无法对消的 `)` ,则不合法。 对于向下的路径,括号对消之后一定得到若干个 `)` 。若遇见无法对消的 `(` ,则不合法。 具体而言需要维护一个栈。 对于向上的路径,后来 `(` 的可以消去前面的 `)`。 对于向下的路径,后来 `)` 的可以消去前面的 `(`。 栈在要记录是否曾经对消,便于回退。 只有消完之后括号数量相同的半路径才能够匹配。 注意,题目中求的是括号序列的“最大深度”所以还要维护这个东西。 抽象成`+1-1`前缀和就容易维护了,注意还要考虑栈中未对消的括号。 由于路径长度是$O($分治块大小$)$的,开个桶维护一下就好了。 这是取$\max$,贡献不可减,桶是支持动态加入的,那就沿用依次加入各个子树的方法。 我们可以把向上的路径加入桶,而用向下的路径来查询。不过这样就变成了有序对,需要正反各做一次。 [评测记录](https://www.luogu.com.cn/record/33194554) - [P3714 [BJOI2017]树的难题](https://www.luogu.com.cn/problem/P3714) 需要保存每条路径端点的颜色,如果两条路径端点颜色相同,则会减去一次贡献(可能是负数)。 有路径长度的限制,仍然考虑线段树维护。 现在我们要同时考虑端点颜色和子树编号两个限制,似乎有点麻烦。但是能够发现,端点颜色是取决于子树编号的。 我们把所有路径按照端点颜色为序,一次加入一个颜色,这就计算完毕了不同颜色之间的贡献,而且不会在同一子树内重复。 然后,我们对于每一种颜色,再分别按照子树编号依次加入即可,此时需要减去一次贡献。 注意清空线段树,这里并不需要标记。还要注意单独考虑从根向下的路径。 这题比较卡常数,$O(n\log^2 n)$似乎并不是正解,但随手加几个最优性剪枝就飞过去了。 [评测记录](https://www.luogu.com.cn/record/33195444) - [P5306 [COCI2019] Transport](https://www.luogu.com.cn/problem/P5306) 仍然是分上下讨论。我们钦定向上的路径包含根。 记录所有向上能到达根的路径,最多余下多少油。 我们一边向下`dfs`,一边维护油量的“最深坑”,也就是负得多惨。 我们要保证一路的油量都大于等于$0$,开始时的油量就不低于“最深坑”。 所有向下的路径,抵达终点需要在初始时额外支付多少油。计算方法类似。 然后排序再双指针扫一下,由于是求和问题,可以采用容斥的办法。 [评测记录](https://www.luogu.com.cn/record/33195776) - [P4183 [USACO18JAN]Cow at Large P](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p4183-usaco18jancow-at-large-p) 先推一些性质,然后容斥,转化成偏序问题。多询问的离线回答技巧。 - [[DP记录]P2305 [NOI2014]购票](https://www.luogu.com.cn/blog/command-block/post-ji-lu-p2305-noi2014-gou-piao) 按重心划分的树上`CDQ`,优化一类按顺序转移的斜率优化`DP`问题。 # 按重心移动 - **例题** [P4886 快递员](https://www.luogu.com.cn/problem/P4886) **题意** : 给出若干个点对,要求选定一个点$c$。 点对$(u,v)$的花费定义为$dis(c,u)+dis(c,v)$,问如何选定$c$使得所有点对花费的最大值最小。 考虑先随意使某个点为$c$,求出各个点对的花费,此时为两个点深度的和。 找出花费最大的点对(们)。 如果$c$在点对间的简单路径上,即点对在不同子树内,答案不可能变小。 又或者多个最大值分布在不同的子树内,答案同样不能变小。 反之,$c$只有向着最大点对所在的子树移动,才可能让答案变小。 于是,我们排除了其余各个子树。这相当于只递归一边的点分治。 我们每次找出点对需要遍历整棵树,是$O(n)$的,只需要$O(\log n)$(分治树深度)次,总复杂度是$O(n\log n)$的。 注意,由于是跳跃移动,答案可能反而变劣,需要不断取$\min$。 还有`grt`中覆盖`vis`的情况需要先判掉`return`。 [评测记录](https://www.luogu.com.cn/record/33189740) - [[??记录]CF566C Logistical Questions](https://www.luogu.com.cn/blog/command-block/post-ji-lu-cf566c-logistical-questions) 利用凸函数的性质和导数,能够得出答案在根的那一边。 - [ 神奇的题目-安排.png ] **题意** : 给出一棵树,有边权。安排一个有序点集$P$使得$|P|=k$。保证$k$是偶数。 需要令$\sum\limits_{i=1}^kdis(P_i,P_{i+1\bmod k})$最大。 首先考虑如果给出一个点集,我们要怎么安排顺序使得答案最大。 能够发现是找到重心,答案就是各个点到重心距离的两倍。 考虑构造 : 在重心的不同子树之间穿插,使得路径总是经过重心。 由于最大子树不超过$k/2$(即便是散点集,边加了权,仍然有这个结论),一定能造出来。 如果任何一个路径不经过重心,答案都会变小。 然后考虑利用重心的性质。先猜测一个重心,在各个子树中贪心地选取深度前$k$大的点。 如果我们猜中了最优答案,没有一个子树选取的点数会超过$k/2$。 我们先要证明,这是答案最优的充要条件。结论 : 重心到点集距离和最小。 假设我们已经有一个符合如上要求的重心$v$,但另有最优解$u$在旁等候。我们可以令$u$中选定的点集连接到$v$上,这会使得距离和增大(因为$v$不是他们的重心),然而这和$v$是局部最优解矛盾。 如果很不幸,某个子树选取的点数超过了$k/2$,我们很有理由怀疑,更优的重心在其所指的方向。 我们可以将此时的点尽量穿插配对,然而在最大的子树内,仍然有一些点无法和外面配对。 如果我们让重心远离它们,这样它们会“变深”,身后的少数点会“变浅”。这样,反而会助长最大的子树的扩张。 所以,为了让没有一个子树选取的点数会超过$k/2$,我们必须向着最大的子树进发。 按照套路,每次向着子区域的重心移动,复杂度是$O(n\log^2n)$的。 注意,当$k$为奇数的时候,可能出现两个子树选满$(k-1)/2$个点,而最后一个点不知道选在哪边的情况,似乎是不太可做的。 # 边分治 点分治中,我们每次统计“只统计经过中心的路径” 边分治中,我们每次统计“只统计经过某条边的路径”。 这条边的选取也很讲究,需要选择两侧联通块尽量均匀的那一条。方法类似。 直接上的话,复杂度是不对的,给一个菊花图就卡掉了。 我们可以添加一些虚边虚点,使得整个图的度数不超过$3$,称之为三度化。这样子就能切得比较均匀了。 注意,这些新加入的东西不能影响答案,一般边权为$0$。如图:  由于三度化和虚边虚点处理,边分治一般要比点分治难写。 边分治有什么好处呢?每次分治的时候,子问题只会被切成**两半**,这会带来一些好的性质。 建议先使用边分治写点分治的题来熟练,如 `P4149`。 先不写三度化体验一把`TLE`的快感。 边分治时,找到分治边后,需要将其删除,此时用邻接链表较为方便。 [评测记录](https://www.luogu.com.cn/record/33699737) ,常数并不大。 - **例题** [ 奇怪的题目.bmp ] **题意** : 给出一棵树,边有两种边权$A,B$。 要求挑选出一条路径,使得$A$权值和在不超过$[L,R]$内,且$B$权值的异或和最大。 先以任意一个点为根,预处理出从根到每个点的异或和$w[u]$。 由异或的自反性,两个端点的$w$值`xor`起来就是路径异或和。 考虑点分治,现在$A$权值和被转化成了两个深度和,这一维的限制变成了偏序。 我们发现,我们只能建立**静态**的可持久化`01Trie`来应付查询,但是这里的贡献不可减,无法容斥。 所以我们转而采用边分治。在边分治中,只有两个子树。 我们只需要在其中一个建立静态结构,然后从另一个出发查询即可。 事实上,点分治如每次合并(直接重建)两个最小的静态结构,并且处理之间的询问,复杂度仍然是正确的。边分治在比较经典的题目中没有多大优势。 - [[DS记录]P4220 [WC2018]通道](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p4220-wc2018-tong-dao) 边分治之后,点只有两种属性。 - [[DS记录]P4565 [CTSC2018]暴力写挂](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p4565-ctsc2018-pu-li-xie-gua) 边分树是二叉树,我们可以类似线段树合并那样写边分树合并。贡献可能在合并时能够顺便计算。 # 链分治 我对这东西没啥很好的理解,暂且随便一讲。 对于路径统计问题,还有另一种思路 : 钦定一个根变为有根树,并且枚举`LCA`。 一般来讲,我们会按照`dfs`的顺序来逐次访问各个节点,这样,我们就能够挑选某个儿子来继承信息。这或许能够改善复杂度。 先将这棵树按照某种规则进行链剖分,即为每个点选择一个“重儿子”,优先`dfs`并保留信息,并将其他轻儿子的信息加入。 在加入信息之前,我们计算新信息与旧信息之间的贡献,不难发现他们代表的路径的`LCA`一定是当前点。 能够注意到,我们必须维护支持动态加入的数据结构(或者二进制分组?)。 - 如果加入的复杂度和**子树大小**相关,这就是**重链剖分**。 选取子树大小最大的儿子作为重儿子。其余的轻儿子都不会超过整颗子树大小的一半。 复杂度是轻儿子子树大小的和,可以转化为每个点上方的轻边条数。 而每经过一条轻边,子树大小至少减半,所以轻边条数是$O(\log n)$的,总合并次数是$O(n\log n)$的。 其实就是`dsu on tree`,树上启发式合并。 - 如果加入的复杂度和**子树最大深度**相关,这就是**长链剖分**。 选取子树深度最大的儿子作为重儿子。 复杂度是轻儿子子树深度的和,可以转化为长链的长度和。 由于长链不交,总合并次数是$O(n)$的。十分优秀 顺便一说,在这里轻儿子子树大小的和是$O(n\sqrt{n})$的。 考虑越往上长链严格越长,而总长度不超过$n$,所以向上只有可能经过$O(\sqrt{n})$条不同的长链。 其实可以看做一次删去一条链,`dfs`的行为也是如此。 某些时候,这类方法也不止于路径统计问题。 - **例题①** [P4149 [IOI2011]Race](https://www.luogu.com.cn/problem/P4149) (**树上启发式合并**) 我们可以用平衡树维护深度和边数,区间取$\min$即可。 树上启发式合并维护,复杂度是$O(n\log^2n)$或$O(n\log n)$,本质上是在重链剖分。 其实直接写线段树合并会达到货真价实的$O(n\log n)$,但是似乎脱离了我们链分治的分析。 - **例题②** [CF208E Blood Cousins](https://www.luogu.com.cn/problem/CF208E) (**长链剖分**) 注意到允许离线,我们用栈+`dfs`就能够轻松求出某个点的$k$级祖先。 现在问题就变成了 : 某个点子树内,距离该点为$d$的点的个数。 我们维护$f[u][d]$表示点$u$子树内,距离该点为$d$的点的个数。 不难发现,状态量和子树最大深度相关,我们采用长链剖分维护这个$dp$。 轻儿子的继承直接加法,是$O(n)$的。 重儿子的继承是难点,需要巧妙的分配空间。善用指针。 如果$v$是$u$的重儿子,把$f[u][1...len[u]]$分配给$f[v][0...len[v]]$,这样直接传上来就符合定义。 其他的题目可能没这么幸运,可能要对这些信息批量操作。 [评测记录](https://www.luogu.com.cn/record/33228321) - **例题③** [CF375D Tree and Queries](https://www.luogu.com.cn/problem/CF375D) (**dsu on tree**) 考虑朴素的树上启发式合并,用数组维护每个颜色出现的次数,以及出现$\geq i$次的有几种颜色,不难做到$O(1)$增量。 但是数组需要的空间较大,且不和时间(子树大小)有关,我们不能为一路上的每一个重儿子都开一个数组。 考虑如何只采用一个全局数组来维护。 先计算轻儿子内部的答案,并将其对全局数组的影响清除。(只是完全清除而已,不一定需要贡献可减) 然后计算重儿子的答案,并将其信息保留并且继承。 然后再次计算轻儿子的影响,和(之间的)贡献。 这种算法被一些人称之为 `dsu on tree`。 复杂度仍然是轻儿子子树大小的和,$O(n\log n)$ [提交记录](https://www.luogu.com.cn/record/26499203) - 附送简单题 [CF600E Lomsat gelral](https://www.luogu.com.cn/problem/CF600E) - [U92408 树](https://www.luogu.com.cn/problem/U92408) **题意** : 给出一棵树,定义$F(S)$为连通点集$S$所需的边数。求$\sum\limits_{i=1}^n\sum\limits_{j=i}^nF([i,j])$。 可以对于每条边分别考虑贡献。 发现跨越某条边的区间数不容易计算,但是不跨越的区间数较为容易。我们只需要分别考虑子树内和子树外。 我们其实就是要维护一堆位置包含了多少个区间。 考虑`dsu on tree`子树内在加入,子树外在删除。 对于子树内的,我们可以采用并查集维护。对于子树外的,可以用类似`ODT`的办法。 重儿子继承比较简单。但是影响清除只需要把并查集指针恢复原样,`ODT`初始化为一整个大区间即可。 复杂度是$O(n\log^2n)$。 [提交记录] () ```cpp ``` - [[DS记录]P4292 [WC2010]重建计划](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p4292-wc2010-zhong-jian-ji-hua) 01分数规划后,转化成给定边数区间的树上最长链。采用长链剖分+线段树。 # 点/边分树 - **点分树** 每次分治的时候,让各个子树的分治中心连接到当前中心上。这棵树的高度是$O(\log n)$的。 不难发现,任意两个点 $x,y$ 的点分树上`LCA`一定在原树中,两点的简单路径上。 而且在$x,y$的公共祖先中,`LCA`是唯一满足这个性质的。 点分树不一定是二叉树。 - **边分树** 每次分治的时候,新建虚点代表一条边,让两个子树的分治中心连接到当前虚点上,如果子树只有一个点则直接连接。这棵树的高度也是$O(\log n)$的。 不难发现,任意两个点的点分树上`LCA`所代表的**边**,一定在原树中两点的简单路径上。 而且在$x,y$的公共祖先中,`LCA`所代表的边,是唯一满足这个性质的。 边分树一定是二叉树。 在这一节中,我们更多地用它们来建模。 - [[DS记录]CFgym101234D Forest Game](https://www.luogu.com.cn/blog/command-block/post-ji-lu-cfgym101234d-forest-game) 问随机点分治复杂度,优雅地利用了点分树的性质。最终转化为点分治+卷积。 - [ 神奇的题目-点分治.png ] **题意** : 给出一棵树,问点分治的方案数。两个方案不同当且仅当某一个连通块所选的点分治中心不同。 $n\leq 5000$。 这相当于点分树计数。我们需要设计一个树形`DP`,但是树上的某**边**对点分树的影响比较难以分析。 我们考虑断开一条边$u,v$之后,如何拆分点分树。 设边一侧的点为白点,另一侧为黑点。对于每个点向上找到大点分树上的第一个同色祖先为父亲。 性质 : 任意两点的点分树上`LCA`,一定在原树中两点的简单路径上。 根据联通块的性质,可以推导出 : 如果两个点同色,则原树路径上的点都同色。 这也就是说,点分树上两个点同色,则它们的`LCA`与其同色。这就能证明两种颜色的点都各自连成一棵树(而非森林)。 反过来考虑,如果我们连接了一条边$(u,v)$,如何合并点分树。也就是说考虑什么样的大点分树能够拆成这两个小的。 容易得到 $u,v$ 合并后必然在同一条直上直下的链上,除此之外的约束只有父子关系。 一个结论是 : 我们只需要考虑把 $u$ 到点分树根的路径和 $v$ 到根的路径按任意顺序归并。 为啥不能动旁边挂着的子树呢? 其实我们可以证明分裂时,$u$到点分树根的路径上挂的树都是纯色的。 考虑反证,如果颜色不纯,则会与其他的异色点呼应产生`LCA`,而这个`LCA`正是$u$到点分树根的路径上的点,矛盾。 经过上述一阵毒瘤的推导,我们现在只需要关注子树的根节点在点分树中的深度。 设$f[u][i]$为点$u$的子树建立点分树,$u$本身深度为$i$的方案数。 在把$u$与儿子$v$贡献合并的时候有: $f'[u][i]=\sum\limits_{j=1}^i\sum\limits_{k=i-j}^{siz[v]}f[u][j]*f[v][k]*\dbinom{i-1}{j-1}$ 组合数这里减一是因为钦定了第$i$位。注意,归并方案数和$k$无关。 对$f[v][k]$做一个后缀和,再加上子树大小剪枝,就可以做到$O(n^2)$了。 # 动态 · 树分治 特意把标题加个点,不要搞错了。 众所周知,猫树是序列上的点/边分树,那么某些东西猫树能(动态)做,点分治能做,就说不定能上点分树。下面可能点分和边分傻傻分不清。 点分树的祖先节点相当于把从 $u$ 出发的所有目的地划分成了$O(\log n)$个联通快,而且有必经点,所以方便处理。 动态链分治不知道该怎么更通俗地描述,因为这东西恐怕只存于树中。大概就是考虑路径所经过的最高重链,以及最高处是轻链的情况。 - **例题①** [P3241 [HNOI2015]开店](https://www.luogu.com.cn/problem/P3241) 没有修改,但是强制在线。应该是难度最低的点/边分树套数据结构了。 图已经三度化,考虑边分治。从$u$开始在边分树上向上跳,会经过$O(\log n)$条关建边。 在每条关建边处,查询**对面**年龄范围内的点的距离和,注意要加上点数$\times$自己到关键边的距离。 这可以排序+前缀和维护,需要二分来查找界限。 到关建边的距离(深度)可以分层来存储。善用指针代替`vector`分配你的内存。 复杂度为$O((n+q)\log^2n)$,空间复杂度是$O(n\log n)$。 [评测记录](https://www.luogu.com.cn/record/33268906) 注意到答案是求和的形式,可以容斥成对前缀的询问。 这就可以采用可持久化边分树来做,按照年龄依次加入修改得到前缀的状态即可。 具体来讲,需要维护已经存在的深度和,以及个数和,这只需要$O(1)$个变量存储就好了。 可持久化的时候,需要把到根的路径`path copy`,还要记录往哪边走,具体见代码。 复杂度为$O((n+q)\log n)$,似乎比可持久化树剖时空双优,但是仍然打不过。 [评测记录](https://www.luogu.com.cn/record/33323522) - [[DS记录]CF757G Can Bash Save the Day?](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-cf757g-can-bash-save-the-day) 在前一题中可持久化边分树的解法基础上,加入了修改。需要写三度化。 - **例题②** [P4115 Qtree4](https://www.luogu.com.cn/problem/P4115) **题意** : 维护带负权的点集最长直径,支持对点集插入和删除。 由于带负权,直径的经典结论不再生效。 ① **动态点分治** 按照点分树深度用$O(\log n)$个数组存下距离信息。 对每个分治中心,每颗子树维护一个可删堆。 对于各个子树的堆顶再维护一个可删堆,我们每次取出第一和第二即可。(若采用边分治可省去) 对于全局的答案,还要维护一个可删堆。 总复杂度是$O(n\log n+m\log^2n)$,空间是$O(n\log n)$。 ② **动态链分治** 我们从被修改的点向上更新,只会经过$O(\log n)$条重链。 考虑某条重链, $d[i]$是 $i$ 号点沿轻链下行的最长长度, $s[i]$ 是重链上两点的距离前缀和。 我们要在答案路径经过的**最高重链**将其捕捉,这相当于维护最大的 $[i<j]d[i]-s[i]+d[j]+s[j]$。 分别维护 $(d[i]-s[i])$ 和 $(d[j]+s[j])$ 的区间最大值,然后`pushup`时更新跨过中线的贡献即可。 向上更新的 $d$ 可以取用本条重链 $(d[j]+s[j])$ 的最大值。 只有对 $d$ 的单点更新,可以(每条重链分别)使用线段树维护。全局的路径再使用一个堆维护。 注意,某个点的 $d$ 可能有多种来源(多个轻儿子),所以不能直接赋值,需要用可删堆维护。 我们还需要考虑路径的最高点不是重链而是轻链的情况,这等价于在维护 $d$ 的堆里面取出最大值和次大值。 复杂度是$O(n\log n+m\log^2n)$,常数较小。[评测记录](https://www.luogu.com.cn/record/33588040) - [SP2939 QTREE5 - Query on a tree V](https://www.luogu.com.cn/problem/SP2939) 现在变成指一个点询问最近的白点,而不是整体问题。 考虑这个点所在的重链,对应着前缀查询 $d[i]-i$ 的最大值,或者后缀查询 $d[i]+i$ 的最大值。 注意,可能与本点的(其他)轻链组成答案,同样在可删堆里面搞搞。 维护 $d$ 是类似的。 [提交记录](https://www.luogu.com.cn/record/33591563) 点分治当然也能做,由于绕路一定不优,可以不处理重复的贡献,代码较短。[提交记录](https://www.luogu.com.cn/record/33592869) - **例题③** [P6329 【模板】点分树 | 震波](https://www.luogu.com.cn/problem/P6329) **题意** : 树上单点修改,每次查询到$u$的距离不超过$d$的点的权值和。 强制在线,$n,m\leq 10^5$ ,时限$\texttt{2s}$. 在没学点分树之前一直以为这东西不可做。 这个模板题并不是最简单的点分树,如果我还能找到更简单的就会更新。 - 退化为链时猫树咋做 对于每个分治区间,考虑跨越中点的点对的贡献。 如果 $u$ 不在分治区间内,无贡献。 如果 $u$ 在左/右边,会查询另一半的前/后缀和。然后在所在的一半分治下去。 修改只会改动 $O(\log n)$ 层的前/后缀和,树状数组就好了。 - 单组询问点分治咋做: 如果 $u$ 不在当前分治区域内,跳过。 如果 $u$ 在当前分治区域内,设 $u$ 到关键边的距离为 $k$。 查询**其他子树**到根距离不超过 $d-k$ 的部分的权值和,然后就变成子问题了。 - 多组询问点分树咋做: 对每个分治中心,维护每颗子树的以深度为下标的权值前缀和。 可以树状数组,大小只需要开到深度即可。总空间$O(n\log n)$. 询问时会在$O(\log n)$层的分治块求和。需要求整体的和再减去自己子树内部的贡献,如果写边分治则无需考虑。 每次单点修改时,会修改$O(\log n)$层的分治块,可以树状数组维护。 总复杂度是$O(n\log n+m\log^2n)$ [评测记录](https://www.luogu.com.cn/record/33291898) 链分治并不太能做,因为轻链只能传递少量信息(适合传统的单路径统计),而这个题需要以深度为序的较多信息。 - **全局平衡二叉树** 用于解决树链操作这一经典问题。 显然是可以直接树剖做的,但是复杂度为$O(n\log^2n)$。 `LCT`的复杂度是$O(n\log n)$,但是常数过大,实际效率并不会更优秀。 现在就要祭出上古魔法 : “全局平衡二叉树”。(可见《QTREE解法的一些研究》,2007) 树剖无疑比`LCT`更加轻便(指思想和分析)。轻重链的选择十分自然,每条重链都用完美平衡的静态结构来维护(虽然更多人的做法是写一个大结构)。可惜的是,复杂度是$O(n\log^2n)$。 究竟是什么设计,让`Splay`胜过完美平衡的静态结构呢? 我们考虑学着`LCT`把轻边拎着的重链的维护结构,挂在真正的父亲上,而且认父不认子。 我们引用一张古老论文里的例图,顺便一睹全局平衡二叉树的真容:  (“二叉树”这个称呼似乎不那么精确,应该称“二叉树森林”或者“多叉树”,取决于算不算轻边) 若要链操作,而在一条重链上区间操作,从全局树上看,下一条待命的重链正好挂在上一次结束的点上。 我们惊奇的发现,这棵全局树的深度,正对应链操作的复杂度! 而树剖的结构只是局部平衡,连上轻边之后可能导致深度增加到$O(\log^2n)$。 (不过倘若不刻意卡,常数会很小。而另一个好处是可以询问和操作子树。) 下一步是试图造出一棵深度为$O(\log n)$的全局树。 若要做到这一点,我们必须认识到 : 单条重链结构的点不止代表了自己,还代表着挂着的一大堆虚子树。 我们可以设$s_i$为重链上第$i$个点本身以及挂着的一堆东西的总大小。这些玩意必须按顺序组成一棵排序树。 我们将其排成一排,找到“重心”,也就是把左右两边分得尽量平均。然后将重心作为根,两侧递归建树。 我个人更习惯`Leafy`的结构,因为更便于拆分区间和可持久化。如果需要构建这样的结构,这里的“重心”就要变为类似边分治的“关建边”。 我们来证明复杂度 : 加权找重心是危险的,因为大块头往往会令人失算。 先不考虑重心及其连带着的部分,不难证明,剩下的两部分都总是小于$(\sum s_i)/2$的。 而重链的性质很好,被我们拎出来的重心挂着的轻儿子总和,同样不会超过整个子问题规模的一半。 这就证明了全局树的深度是$O(\log n)$的。我们构造时的复杂度不超过其每个点的子树大小和,为$O(n\log n)$。 这棵树是静态结构,常数较小,复杂度货真价实,也并不难实现。 - 附送练习题 : 1. [P4211 [LNOI2014]LCA](https://www.luogu.com.cn/problem/P4211) 非常适合的练手题,然而这个做法并没有多大的效率优势。[评测记录](https://www.luogu.com.cn/record/33298489) 2. [P4719 【模板】"动态 DP"&动态树分治](https://www.luogu.com.cn/problem/P4719) 结合`ddp`的理论,优化较为明显。[评测记录] () 实际上,大多数的操作都可以跳父亲无递归实现,这和点分树有点类似。 可能你发现了,这些操作都是到根的。实际上,不到根的路径操作(区间而非前缀)如噩梦般难写,如果遇到了还是弃疗写树剖吧…… 如果将同一个点上挂着的轻儿子,同样使用加权二叉树维护,似乎就能够做到子树操作(静态`Top tree?`)。 - [[DS记录]P3345 [ZJOI2015]幻想乡战略游戏](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p3345-zjoi2015-huan-xiang-xiang-zhan-lve-you-hu) 利用重心的一些(很多)性质,包括带权的和不带权的。 - [P3920 [WC2014]紫荆花之恋](https://www.luogu.com.cn/problem/P3920) **题意** : 给出一棵带权树,每个点有参数 $r[u]$ ,求 $r[u]+r[v]\geq dis(u,v)$ 的点对数目。 由于这样太简单了,还需要支持挂叶子。强制在线。 $n\leq 10^5$ ,时限$\texttt{12s}$。 真正的毒瘤 到 来 了 。 先不考虑挂叶子,进行普通点分治。 每次选定分治中心之后,答案是 $dep[u]+dep[v]\leq r[u]+r[v]$ 的点对数目。 可以变成 $dep[u]-r[u]\leq r[v]-dep[v]$。使用平衡树维护。 挂叶子的时候,我们可以暂且在点分树中,先将其挂在父亲的下面。 沿着点分树一路向上更新,会有 $O(h)$ 个计算路径长度(需要倍增),以及平衡树插入操作。 然后需要查询贡献。在每个分治中心处,需要查询其他子树的贡献。 这可以维护一个大平衡树,再给每颗子树维护一个小平衡树,查询两次减去即可。 但是,随着叶子越挂越多,点分树的深度 $h$ 也会变深,将会导致复杂度退化。 一个憨逼的想法是 : 模仿替罪羊树,重构不平衡的局部点分树。 重构的时候其实就是局部点分治,由于需要 `sort` 建立平衡树,复杂度是两个 $\log$ 的。 可以考虑对较大的数组基数排序。具体地讲,在 $O(n\log n)$ 和 $O(n\log_nS)$ 之间权衡,这样可以把排序的 $\log n$ 摊平成 $\sqrt{\log S}$ ,而且不会增大常数。 传统替罪羊的重构比修改低一个 $\log$ ,此时 $\alpha=0.75$ 才比较快。 本题中而重构复杂度较大,则需要把 $\alpha$ 调大一点 (如 $\alpha=0.8$ )。 > 仔细分析,将替罪羊在最差情况下理解成类 $a$ 进制分组,则重构的复杂度是 `lowbit` 求和,为 $O(n\log_a n)$ ,修改的复杂度为 $O(an\log_an)$。 > 本题中,这样所能得到的最优复杂度为 $O(n\log^2n\frac{\sqrt{\log S}}{\log\log n})$ (毒瘤,反正比 $O(n\log^3n)$ 要快) 平衡树一定要比较快,不然可能被卡常数。需要写个内存垃圾桶来回收平衡树节点。 局部点分治的时候,可以先跳父亲来封边界。 注意某个联通快块重构之后,父亲还是得更新。 ```cpp #include<algorithm> #include<cstring> #include<cstdio> #include<vector> #define ll long long #define pb push_back #define INF 1000000000 #define MaxN 100500 using namespace std; int read(){ int X=0;char ch=0; while(ch<48||ch>57)ch=getchar(); while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar(); return X; } struct BST_Node {int l,r,x,c;}a[MaxN*66]; int rub[MaxN*66],rut,tn2; int cre(){ if (!rut)return ++tn2; int pos=rub[rut--]; a[pos].l=a[pos].r=0; return pos; } int sx[MaxN],st2[255],tot2; struct BST { #define st st2 #define tot tot2 int rt; BST(){a[rt=cre()].x=INF;a[rt].c=1;} inline void up(int u){ a[u].x=a[a[u].r].x; a[u].c=a[a[u].l].c+a[a[u].r].c; } int find(int x) { int u=rt;tot=0; while(1){ if (a[u].l==a[u].r)return u; st[++tot]=u; if (x<=a[a[u].l].x)u=a[u].l; else u=a[u].r; } } void del(int u){ rub[++rut]=u; if (a[u].l==a[u].r)return ; del(a[u].l);del(a[u].r); } void clr(){del(rt);rt=0;} void pia(int u) { if (a[u].l==a[u].r){ sx[++tot]=a[u].x; rub[++rut]=u;return ; }pia(a[u].l);pia(a[u].r); rub[++rut]=u; } void build(int l,int r,int &u) { u=cre(); if (l==r){ a[u].x=sx[l];a[u].c=1; return ; }int mid=(l+r)>>1; build(l,mid,a[u].l); build(mid+1,r,a[u].r); up(u); } #define chk(u) a[u].c*31 < 40*max(a[a[u].l].c,a[a[u].r].c) void add(int x) { int u=find(x),nu=cre(),nv=cre(); a[nu]=a[u];a[u].r=nu; a[a[u].l=nv].x=x;a[nv].c=1; up(u); int reb=0; for (int i=tot;i;i--){ up(st[i]); if (chk(st[i]))reb=st[i]; }if (reb){ tot=0;pia(reb); build(1,tot,reb); } } int rnk(int x) { int u=rt,ans=0; while(1){ if (a[u].l==a[u].r)return ans; if (x>=a[a[u].l].x) {ans+=a[a[u].l].c;u=a[u].r;} else u=a[u].l; } } #undef st #undef tot }T[MaxN],T2[MaxN]; vector<int> g[MaxN],l[MaxN],tv[MaxN]; void adl(int f,int t,int len){ g[f].pb(t);l[f].pb(len);tv[f].pb(0); g[t].pb(f);l[t].pb(len);tv[t].pb(0); } int st[MaxN],tn,ms[MaxN],siz[MaxN], tef,ef,vis[MaxN]; void pfs(int u) { siz[st[++tn]=u]=1; vis[u]=ef;ms[u]=0; for (int i=0,v;i<g[u].size();i++) if (vis[v=g[u][i]]<ef){ pfs(v); siz[u]+=siz[v]; ms[u]=max(ms[u],siz[v]); } } int grt(int u) { tn=0;ef++;pfs(u); int rt=0; for (int i=1;i<=tn;i++){ ms[st[i]]=max(ms[st[i]],tn-siz[st[i]]); if (ms[st[i]]<ms[rt])rt=st[i]; }return rt; } struct PDC_Node {int f,c,d;}t[MaxN]; int r[MaxN],d[38][MaxN],*td,sd[MaxN],tot; void gdis(int u) { sd[++tot]=td[u]-r[u]; vis[u]=ef; for (int i=0,v;i<g[u].size();i++) if (vis[v=g[u][i]]<ef){ td[v]=td[u]+l[u][i]; gdis(v); } } void qs(int *s,int n) { if (n<=256){sort(s+1,s+n+1);return ;} static int o[260],g[MaxN]; for (register int i=1;i<=n;++i)s[i]+=INF; for (register int i=1;i<=n;++i)++o[(s[i]&255)+1]; for (register int i=1;i<=255;++i)o[i]+=o[i-1]; for (register int i=1;i<=n;++i)g[++o[s[i]&255]]=s[i]; memset(o,0,sizeof(o)); for (register int i=1;i<=n;++i)++o[((g[i]>>8)&255)+1]; for (register int i=1;i<=255;++i)o[i]+=o[i-1]; for (register int i=1;i<=n;++i)s[++o[(g[i]>>8)&255]]=g[i]; memset(o,0,sizeof(o)); for (register int i=1;i<=n;++i)++o[((s[i]>>16)&255)+1]; for (register int i=1;i<=255;++i)o[i]+=o[i-1]; for (register int i=1;i<=n;++i)g[++o[(s[i]>>16)&255]]=s[i]; memset(o,0,sizeof(o)); for (register int i=1;i<=n;++i)++o[(g[i]>>24)+1]; for (register int i=1;i<=255;++i)o[i]+=o[i-1]; for (register int i=1;i<=n;++i)s[++o[g[i]>>24]]=g[i]; memset(o,0,sizeof(o)); for (register int i=1;i<=n;++i)s[i]-=INF; } void build(int u,int dep) { t[u].c=1; (td=d[t[u].d=dep])[u]=0; vis[u]=tef;tot=0; for (int i=0,v,sav,vrt;i<g[u].size();i++) if (vis[v=g[u][i]]<tef){ tv[u][i]=vrt=grt(v); sav=tot; td[v]=l[u][i]; ef++;gdis(v); T2[vrt].clr(); for (int j=sav+1;j<=tot;j++) sx[j-sav]=sd[j]; qs(sx,tot-sav);sx[tot-sav+1]=INF; T2[vrt].build(1,tot-sav+1,T2[vrt].rt); } sd[++tot]=-r[u]; T[u].clr(); for (int i=1;i<=tot;i++)sx[i]=sd[i]; qs(sx,tot);sx[tot+1]=INF; T[u].build(1,tot+1,T[u].rt); for (int i=0,v;i<g[u].size();i++) if (vis[v=g[u][i]]<tef){ t[v=tv[u][i]].f=u; build(v,dep+1); t[u].c+=t[v].c; } } int f[MaxN][18],dis[MaxN],dep[MaxN]; int lca(int x,int y) { int k=17; if (dep[x]>dep[y])swap(x,y); while(k--) while(dep[f[y][k]]>=dep[x]) y=f[y][k]; if (x==y)return x; k=17; while(k--) while(f[x][k]!=f[y][k]) {x=f[x][k];y=f[y][k];} return f[x][0]; } int dist(int x,int y) {return dis[x]+dis[y]-(dis[lca(x,y)]<<1);} int tn3; #define tn tn3 void find(int u) {tn=0;while(u){st[++tn]=u;u=t[u].f;}} ll ans; #define chk2(u) t[t[u].f].c*4 <= t[u].c*5 void add(int u) { find(u); for (int i=1;i<=tn;i++)t[st[i]].c++; int reb=0; for (int i=tn-1;i;i--) if (chk2(st[i])) {reb=st[i+1];break;} if (reb){ tef=ef+(t[reb].c<<2)+10; for (int i=tn;st[i]!=reb;i--)vis[st[i]]=tef; int rt=grt(reb); t[rt].f=t[reb].f;swap(T2[rt],T2[reb]); build(rt,t[reb].d); ef=tef; find(rt); for (int i=2,v,len;i<=tn;i++){ v=st[i]; len=(d[t[v].d][u]=dist(v,u))-r[u]; T[v].add(len);T2[st[i-1]].add(len); }find(u); }else { t[u].d=t[t[u].f].d+1; for (int i=2,v,len;i<=tn;i++){ v=st[i]; len=(d[t[v].d][u]=dist(v,u))-r[u]; T[v].add(len);T2[st[i-1]].add(len); }T[u].add(-r[u]); } for (int i=tn,v,len;i>1;i--){ len=r[u]-d[t[v=st[i]].d][u]; ans+=T[v].rnk(len)-T2[st[i-1]].rnk(len); } } #undef tn int n; int main() { read();vis[0]=INF;ms[0]=(n=read())+1; read();read();puts("0"); T[1].add(-(r[1]=read())); t[1].c=1;dep[1]=1; for (int i=2,u,c,len;i<=n;i++){ t[i].f=f[i][0]=u=read()^(ans%1000000000); adl(u,i,len=read()); dis[i]=dis[u]+len; dep[i]=dep[u]+1; r[i]=read(); for (int j=1;j<17;j++) f[i][j]=f[f[i][j-1]][j-1]; add(i); printf("%lld\n",ans); }return 0; } ```