综合 （动态）点分治算法学习笔记
$$\huge \rm 点分治$$
$$\Large \rm 点分治思想$$
$\quad$点分治用于处理大规模树上路径信息问题。
$\quad$其基本思想是在子树内处理完只跟子树有关的信息，再将其汇总到父节点处。递归时，不是简单地访问当前节点的儿子，而是求出子树的重心，再向这个重心递归。
$$\Large \rm [LG3806]点分治1$$
$\quad$点分治模板题。
$\quad$考虑在结点 $u$ 处求解所有以 $u$ 为拐点的链中是否有长度为 $k$ 的链。遍历时用一个桶记录下所有以 $u$ 为一个端点的链的长度即可。求解完再直接向子树的重心遍历，现在的问题又变成了一个相同的子问题。需要注意的是，所有的结点都会被作为重心统计一次，所以不存在漏掉的情况，利用点分治的遍历方法会让复杂度更优仅仅是因为每次子树节点数减半，而非重复利用了什么信息。
$\quad$时间复杂度 $\Theta(qn\log n)$.
$$\Large \rm [IOI2011]Race$$
$\quad$比前一题多记录一个状态，即每条长度为 $k$ 的链的结点个数，这个很好计算，但需要注意的是，记录结点个数的桶初值需赋为 $\tt INF$，每次修改时取较小值。
$$\Large \rm [国家集训队]聪聪可可$$
$\quad$记一个桶，分别记录三种长度的路径有多少条，将儿子一个个往里加即可。
$$\Large \rm [LG4178]Tree$$
$\quad$点分治 $+$ 树状数组。
$\quad$考虑如何统计在点 $u$ 处的答案。用树状数组记录在当前节点长度为 $i$ 的链有多少条，然后直接对每条新加进的路径查询前缀和即可。
$\quad$时间复杂度 $\Theta(n\log^2n)$.
$$\Large \rm 点分树\&动态点分治$$
$\quad$观察到点分治时作为根遍历的结点也形成一棵树，且它是包含原树中所有节点，树高为 $\log n$ 的重构树，在这棵树上，由于树高为 $\log n$，所以原本一些很不对劲的暴力在这棵树上都能有正确的复杂度。点分树常用于解决与树原形态无关的带修改问题。
$\quad$有如下问题，设计一种数据结构，支持以下操作：
在线查询一个节点 $u$，答案为 $\sum_{v\in T}dist(u,v)\times w_v$.
修改一个节点的点权。
$\quad$考虑建立点分树 $T'$，此时 $T$ 中有用的信息仅有两点间点权，这个可以用树剖 $\rm LCA$ 较快地计算。
$\quad$在 $T'$ 中，$T'_x$ 表示以 $x$ 号节点为根的子树，令 $f_u=\sum_{v\in T'_u}dist(u,v)\times a_v~,~sum_u=\sum_{v\in T'_u}a_v$.
$\quad$统计答案时从当前节点向上跳，假设当前跳到结点 $fa_u$，答案更新为 $ans+f_{fa_u}-f_u-sum_u\times dist(u,fa_u)+(sum_{fa_u}-sum_u)\times dist(fa_u,u)=f_{fa_u}-f_u+(sum_{fa_u}-2sum_u)\times dist(fa_u,u)$. 其意义是，计算所有结点 $v\in T'_{fa_u}\cap~\overline{T'_u}$ 的贡献。
$\quad$考虑对当前算法进行优化，由于遍历到根节点的顺序中，有关 $f$ 的计算为 $f_u+(f_{fa_u}-f_u)+(f_{fa_{fa_u}}-f_{fa_u})+\cdots +(f_{root}-f_{pro_root})=f_{root}$，故不用计算 $f$，只需预处理出 $f_{root}$ 即可。另外，考虑到在计算中关于两点间距离只需求 $dist(u,fa_u)$，所以可预处理出所有 $dist(u,fa_u)$.
$\quad$对于动态点权修改操作，只牵涉到 $f_{root}$ 和 $sum_s(v\in T'_s)$ 的修改，这些都可以在 $\log n$ 的时间内完成。
$\quad$由于在点分树中，树高为 $\log n$，所以暴力向上跳的次数仅有 $\log n$ 次，故总时间复杂度为 $\Theta[(n+q)\log n]$.
$$\Large \rm [LG6329]震波$$
$\quad$点分树 $+$ 权值线段树。
$\quad$令 $f_u$ 为一颗记录 $T'_u$ 中信息的动态开点权值线段树。
$\quad$对于修改点权操作，直接在 $T'$ 中从 $u$ 往上跳，在当前结点的权值线段树中修改点权即可，单次操作 $\Theta(\log^2n)$。
$\quad$对于查询操作，记 $f_{u,0\to k}$ 表示权值线段树 $f_u$ 中，结点距离点 $u$ 为 $0$ 到 $k$ 的点权之和，$g_{u,0\to k}$ 表示权值线段树 $g_u$ 中，结点距离点 $fa_u$ 为 $0$ 到 $k$ 的点权之和，这个可以 $\Theta(\log n)$ 求。查询一个节点 $u$ 的答案时，从 $u$ 开始往上跳，$ans$ 初值为 $f_{u,0\to k}$，每次更新答案 $ans=ans+f_{now,0\to k-dist(u,now)}-g_{pro,0\to k-dist(u,now)}$，单次操作 $\Theta(\log^2n)$.
$\quad$一个简化代码的 $\rm Trick$ : 可以一开始将权值线段树的值都设为 $0$，然后把初始权值看做 $n$ 个修改权值的操作。
$\quad$总时间复杂度 $\Theta[(n+q)\log^2n]$.