[总结] 动态点分治学习笔记
唔突然不想写那么长的总结了
大概思想就是维护一个点分树，这样保证了树高是\(\log\)级别的，然后对于一些修改或者询问，就可以支持诸如在点分树上暴跳\(\text{father}\)这样的暴力做法了。
但是这并不是原来的树，所以在点分树上维护的信息要以原树为准。
具体题目具体分析，但大方向是在点 \(i\) 维护点分树上点 \(i\) 的子树的信息，并且维护点 \(i\) 的子树到点分树上 \(i\) 的父亲的信息。不这样做的话大概会把在原树上点 \(i\) 和点 \(i\) 的父亲（点分树上）之间的联通块的答案多统计，这样维护一下就可以减掉了。
下面是两道题：
[BZOJ3730] 震波
Description
给定一棵树，点有点权。要求支持修改点权，询问距离点 \(x\) 小于等于 \(y\) 的点的点权和。\(n,m\leq 10^5\)。
Sol
这是最经典的维护上面说的两个信息，然后减一下保证答案不重复。
就是在每个点维护两棵以距离为下标的线段树，分别是点分树上点 \(i\) 的子树对于 \(i\) 的点权和，以及点 \(i\) 的子树对于 \(fa[i]\) 的点权和。这样做有什么好处？
考虑询问 \(dis=3\)，我们先在点 \(x\) 求出所有到点 \(x\) 距离小于等于 \(3\) 的点权和，假设 \(dis(x,fa[x])=2\)，那么还要求出点 \(x\) 的子树中到 \(fa[x]\) 距离小于等于 \(1\) 的点权和，然后把这部分答案减去。原因是会在跳到 \(fa[x]\) 时统计所有到 \(fa[x]\) 的距离小于等于 \(3-2=1\) 的点权和，这里会重复统计，所以要提前减去。
[WC2014] 紫荆花之恋
Description
给定一棵空树，每次会向这颗树中添加一个节点，点带权。每次添加完后回答树中有多少节点对满足两点之间的距离小于等于两点点权和。\(n\leq 10^5\)。强制在线。
Sol
先假设是一棵静态的树，怎么求答案？
点分治。
对于所有 \(dis(i,u)+dis(j,u)\leq r[i]+r[j],(i,j)\) 是一对合法点对。移项发现两项独立，于是可以在节点 \(u\) 维护一棵平衡树来统计\(\text{rank}\)。
那动起来怎么办呢？
动态点分治+定期重构点分树。
每次还是加一个节点，然后在点分树上暴跳\(\text{father}\)来统计答案。
但是如果是一条链怎么办？
所以需要像替罪羊树那样定期重构。
然后重构时有一些实现方面的问题，比如说每个点要开两个\(\text{vector}\)记录每个点在点分树上的祖先和在原树上到祖先的距离，还要开个\(\text{vector}\)记录这个点在点分树上的所有儿子。这样做完全是为了方便重构点分树。
具体重构就是，找到最靠上且需要重构的点，然后把它的子树全部扫一遍，求出重心，然后递归去做。说起来挺简单但是有一点细节？记得在平衡树\(\text{pushup}\)的时候\(+1\)，把自己也放进存儿子的\(\text{vector}\)里。就没啥了。
好的又填完一个坑