Shr讲座 点分治与点分树
点分治
对于每个子问题，找出重心，处理跨过重心的链的答案。然后以重心为根（删去重心）分成若干连通块，递归到每个连通块中去，处理每个子连通块的子问题。
如何处理跨过重心的链的答案？可以对于每个子树扫两遍，第一遍计算它与前面子树产生的贡献，第二遍把它自己加到前缀信息中。
trick：树链剖分优化建图。试图建“虚树”，将一个点连向原树上一条链上的点时：可以对原树做树链剖分，并从原树上每个点在新图上对应的点向其父亲连一条有向边（如果它是它父亲的重儿子）；树链剖分时，我们是要向某一个重链的前缀连边，那么直接向这个前缀的下端点连边即可；到了最上面怎么办呢？我们要给dfn连续的一段连边，我们用线段树做就可以了。