数据结构与算法_树上分治（点分治与边分治）

    分治法是指将规模较大的问题分解为规模较小的子问题，解决各个子问题然后合并得到原问题的答案。树上的分治算法分为点分治和边分治。

    分治法的核心是分解和治理。如何分？ 如何治？

    点分治，是一种针对可带权树上简单路径统计问题的算法。本质上是一种带优化的暴力，带上一点容斥原理。对于树上路径，并不要求这棵树是有根树，无根树不影响统计结果。

    1. 对于点分治：重心分解

        数列上的分治法，通常从数列中间进行二等分，也就是说分解得到的两个子问题规模相当。对于树，怎么划分呢？

        树上的划分也要尽量均衡，不要出现一个子问题太大，另一个子问题太小的情况。也就是说期望划分后每个子树的结点树不超过 n/2 。

        那么选择哪个结点作为划分点呢？

        可以选择树的重心。树的重心是指删除该结点后得到的最大子树的结点数最少。删除重心后得到的所有子树，其结点数必然不超过 n/2 。

    求树的重心，只需要进行一次深度优先遍历，找删除该结点后最大子树最小的结点即可。

    用 f[u] 表示删除 u 后最大子树的大小， size[u] 表示以 u 为根的子树的结点数, S 表示整棵子树的结点数。先统计 u 的所有子树中最大子树的结点数，然后与 S-size[u] 比较最大值。如图所示。

    如果 f[u] < f[root] ，则更新当前树的重心为 root = u。

2.  边分治，是指在树中选一条边，使得边的两端最大子树尽可能的小，这条边称为中心边。和点分治不同的是，中心边只会把树分成2棵子树，因此处理起来比较方便，，找中心边的方法和找重心的方法一样，找使最大子树尽可能小的那一条边。

    对于一棵树，假设找到的中心边为 x-y，对于这棵树中的路径只有两种：

•     经过边 x-y;
  

•     不经过边 x-y;
  

    不经过 x-y 的路径在某一端的子树中，只需要递归求解即可。现在只考虑经过这条边的路径信息，处理完当前子树后，删掉中心边，将树分成2棵树，再进行递归操作。如图所示。

   1） 树的重建：

点权：权值在点上。边权：权值在边上。

2）求中心边：

    找中心边的方法和找重心类似，只需要进行一次深度优先遍历，找删除该边后最大子树最小的边即可。

    size[u] 表示以 u 为根的子树的结点树， size[rt] 表示以 rt 为根的子树的所有结点数。如图： 

    如果 max( sz[u]，sz[rt]-sz[u] ) < Max ，则更新 Max ， 中心边 midedge = code。

3）中心边分解

    （1）首先求出中心边 midedge, 得到中心边的两个端点 p1,p2，然后删除 p1 的邻接边 midedge^1,删除 p2的邻接边 midedge。如图所示。

    （2）再分别从 p1,p2出发递归求解；

    （3）更新树根 rt 的 ans。