问题引入:

静态统计一棵树上符合条件的路径数

前置知识:

①分治思想

②求树的重心

重心的定义:

去掉树中任意一个点，可得到多颗子树，设这这些子树的大小为 $a_1,a_2,...,a_n$

重心就是在树中去掉之后 $得到的a_1,a_2,...,a_n中最大的值最小$ 的那个点(又称质点)

重心的一个重要性质:重心的所有子树的 $size <= \frac{n}{2}$

性质的证明:

$\text{[math]}$

每次选取重心为根，对树进行划分。

求重心的思路:

就是一遍dfs.枚举每个点，对于每个点求各个子树的大小，从中选出最小值当做结果，然后更新最小值.遍历完后即得到答案.

$\text{[math]}$

这里递归层数就为三层

$\text{[math]}$

解决了分的问题后，我们要解决“治”的问题（确定T(n)）。也就是如何快速的统计路径个数。

而对于一个根而言,树上的路径分为两种:(1)路径经过根 (2)路径不经过根,这样构成了路径的完整划分.

对于路径(1):

①在本连通分量中，找到重心，将其当作根.

②O(n)遍历一遍树找出每个点离根的距离,dis数组

③选取任意两个点的树链合并成一条路径(包括根自己),这样就把所有的路径(1)找出来了.但是有一个问题，可能这两个点在同一颗子树内，这时我们需要减去这一部分的贡献(简称容斥),等下一层再算的时候需要以它的儿子们为根再额外算一遍路径数,容斥掉这一部分的贡献就好.

对于路径(2):

首先，不管是一棵树还是一条路径，里面的任意节点都可以看成是根。

所以就算路径(2)不过之前的根，但是他总会过某一个根。

所以我们可以拿掉重心，余下来它的子树。对于每一个子树重复进行上述步骤.总会将路径(2)统计完全。

题目清单: