概述
将点分治的过程离线下来，即将重心相连，可以形成一棵树，称作点分树。它有很好的性质
树的深度为 $O(\log n)$。
所有点子树大小为 $O(n\log n)$。
点分树上 $lca(u,v)$ 一定在原树 $u \leadsto v$ 上。
对于任意点 $u$，一般会用数据结构维护 $u$ 的子树的对 $u$ 信息，$u$ 的子树对 $fa_u$ 的信息。后者用于容斥。
例题
1.【模板】点分树 | 震波
建出点分树。对于查询，枚举 $x$ 在点分树上的祖先，统计祖先的子树对答案的贡献，将重复的容斥掉。对于修改，用树状数组维护信息，将 $x$ 在点分树上的祖先都改一下即可。时间复杂度 $O(n\log^2n)$。
2.[HNOI2015] 开店
一棵树，点有点权，多次询问，每次询问点权 $<=k$ 的点到 $u$ 的距离和，强制在线。
由于没有修改，对每个点开个 vector 按权值排序并预处理前缀和，查询时二分一下即可。
3.[ZJOI2015] 幻想乡战略游戏
在点分树上每次向重心移动一步，最后到达重心，移动次数为 $O(\log n)$。
考虑重心确定时如何快速计算答案，类似换根 DP，每次跳父亲计算答案即可。
时间复杂度 $O(n\log^2n)$。
4.小清新数据结构题
设根为 $1$，推式子得到
其中 $siz{[u,1)}$ 为 $u \to 1$ 不包括 $1$ 的 $siz$ 和。树剖简单维护，时间复杂度 $O(n\log^2n)$。
但是现在在学点分树，考虑点分树做法。还是推式子，考虑将平方拆开。
对于前面的，需要快速查询 $\sum_{x}a_xdis(x,u)$。
对于后面的，它和根没有关系，初始值是好求的，当 $a_u+v$ 时，它增加 $2v\sum_{x}a_xdis(x,u)$。
点分树，时间复杂度 $O(n\log n)$。
5.[Ynoi2011] 成都七中
对于询问 $(l,r,u)$，可以将每个点到 $u$ 路径上的最大/小编号预处理出来，记为 $(x,y)$。
那么点 $(x,y)$ 与 $u$ 在同一个连通块当且仅当 $l \le x,y \le r$。扫一遍求解，时间复杂度 $O(mn)$。
只要 $u,v$ 在同一连通块中，那么 $(l,r,u)$ 与 $(l,r,v)$ 答案相同。
建出点分树，求出点分树上与 $u$ 在同一连通块的最浅点 $v$，此时询问变为 $(l,r,v)$，好处是点分树的子树和为 $O(n\log n)$。
对于 $v$ 的求解可以在点分树上暴力往上跳，用倍增维护路径最大/小编号，还可以预处理点分树上每个点到祖先节点路径的最大/小编号。
一个点会挂多个询问，离线树状数组求解，时间复杂度 $O(n\log^2n)$。
6.Iqea
保证剩余部分也连通。
考虑将极长行连通块缩成一个点，将相邻点连边，形成一棵树。
树上动态加点，求距离最小点，考虑点分树。
考虑如何通过中间点计算答案，需要计算某点到特定连通块的距离，用 bfs。
拆式子，需要对连通块每个点维护前后缀最小值。
7.[WC2014] 紫荆花之恋
需要每加入一个点时将与它相关的点对的数量求出来，再加入该点。
如果不强制在线，那么可以先建出点分树。需要支持加入，查询比 $v$ 小的数的个数。可以用平衡树。
还有一种根号分治的做法。维护两个 ‘vector’ A、B，在 $A$ 中暴力加入点 $v$，若 $|A| > S$ 那么对 A,B 进行归并排序，将 A 清空。查询时在 A,B 中二分即可。
由于强制在线，考虑设计一个平衡因子 $\alpha$，若存在 $siz_u > \alpha siz_{fa_u}$，那么将 $fa_u$ 的子树重构，这样来维持点分树的高度为 $O(\log n)$。取 $\alpha=0.9$ 较优。
取 $S=\sqrt{n}$ 可以做到 $O(n\sqrt{n}\log n)$。
实现上一堆细节，具体看代码。