点分树
算法简介
点分治的动态版本，可以动态维护树上路径信息，一般会与线段树或平衡树等数据结构配合使用。
特别适用于一些需要维护与路径长度相关信息的题目。
一般空间复杂度为 $O(n\log n)$，单次查询或修改时间复杂度为 $O\left(\log^2 n\right)$，常数极大，慎用。
算法思想
把点分治过程中得到的重心连接，得到一棵虚树，该树有如下性质：
1、深度不超过 $\log n$。
2、所有结点的子树大小和不超过 $n\log n$。
由于点分治最多递归 $\log n$ 层，所以性质一成立。
对性质二，考虑每个结点对子树大小和的贡献。
每个结点对每个祖先结点(包括它自己)产生一个贡献，而由性质一，每个节点最多有 $\log n$ 个祖先结点，所以每个结点贡献最多为 $\log n$。
所以有所有结点的子树大小和不超过 $n\log n$，性质二证毕。
有了这两个性质的保障，便可以用点分树暴力地解一些题目。
一般思路为对每个结点，维护该结点在虚树中的子树信息。
对每个结点，若使用线段树或平衡树等数据结构维护子树信息，根据性质二，空间复杂度仅为 $n\log n$。
修改和查询都暴力跳 $\text{fa}$ ，若每次查询线段树或平衡树数据结构维护子树信息，根据性质一，有单次查询或修改时间复杂度为 $O\left(\log^2 n\right)$。
算法习题
习题一
题意
给出一棵 $n$ 个结点的点权树，相邻点距离为 $1$ ，接下来 $m$ 个操作，操作有以下两种：
操作0：输出所有到结点 $x$ 距离不超过 $k$ 的结点的点权和。
操作1：将结点 $x$ 点权修改为 $y$。
同时算法要求强制在线，对每次操作的参数 $x、y、k$，都需要异或上一次输出的答案。
题解
考虑对每个结点，建立两个树状数组，第一个树状数组维护所有在虚树中属于结点 $x$ 的子树且到 $x$ 距离等于 $k$ 的点权和的数组。
第二个树状数组维护所有在虚树中属于结点 $x$ 的子树且到结点 $x$ 在虚树中的父亲的距离等于 $k$ 的点权和的数组。
记 $\text{dist}(x,y)$ 为结点 $x$ 到 $y$ 距离，可以用树剖或者欧拉序列加 $\text{ST}$ 表求。
对查询操作，可先查询 $x$ 第一个树状数组中距离小于等于 $k$ 的点权和。然后开始暴力跳 $\text{fa}$。
每次加上 $\text{fa}$ 结点第一个树状数组中距离小于等于 $k-\text{dist}(x,fa)$ 的点权和。
但是这样会重复计算 $\text{fa}$ 结点的子结点的子树贡献。
所以再减去 $\text{fa}$ 结点的子结点的第二个树状数组中距离小于等于 $k-\text{dist}(x,fa)$ 的点权和。
最后便可以得到答案，时间复杂度为 $O\left(\log^2 n\right)$。
对于修改操作，需要同时维护每个结点的第一个和第二个树状数组。
同样先修改 $x$ 第一个树状数组中距离为 $0$ 的点权和(因为 $x$ 到自身距离为 $0$ )。然后开始暴力跳 $\text{fa}$。
每次修改 $\text{fa}$ 结点第一个树状数组中距离为 $\text{dist}(x,fa)$ 的点权和。
再修改 $\text{fa}$ 结点的子结点的第二个树状数组中距离等于 $\text{dist}(x,fa)$ 的点权和。
最后便可以完成修改，时间复杂度也是 $O\left(\log^2 n\right)$。
习题二
题意
给出一棵 $n$ 个结点的树，相邻点距离为 $1$ ，一开始所有点都为黑点，接下来 $m$ 个操作，操作有以下两种：
操作1：改变结点 $x$ 的颜色(黑色变白色，白色变黑色)。
操作2：询问树上距离最远的黑色点对的距离，如果只有一个黑点输出 $0$ ，如果没有黑点输出 $-1$。
题解1
考虑对每个结点 $x$ ，建立两个大根堆，第一个堆维护每棵在虚树中属于结点 $x$ 的子树到结点 $x$ 的最大距离。
第二个堆维护所有在虚树中属于结点 $x$ 的子树的结点到 $x$ 在虚树中的父亲结点的距离。
最后建立一个答案堆，维护每个结点的答案，其中每个结点的答案为每个结点第一个堆的最大值和次大值和。
对于操作1，同样是暴力跳 $\text{fa}$ ，沿途维护结点的第一个堆和第二个堆。
关于堆的删除操作，可以考虑建两个堆，如果第一个堆存所有的数，第二个堆存要删除的数。
每次取第一个堆最大元素前先检测两个堆顶元素是否相同，相同则同时 $\text{pop()}$。
另外，求两个结点的距离好像可以通过 $bfs$ 预处理完成，可以避开欧拉序列加 $\text{ST}$ 表常数过大的问题。
记 $\text{dist}(x,y)$ 为结点 $x$ 到 $y$ 距离，可以用树剖或者欧拉序列加 ST 表求。
对于操作2，直接查询答案堆最大元素即可。
具体一些细节见代码。
题解2
这个解法和点分树没什么关系，用的是括号序列加线段树，时空间复杂度都比点分树少一个 $\log$。
这里仅提供代码，有兴趣的可以自行学习。
