别让执念毁掉了昨天

来看一道简单题

IOI Tree

题目描述

给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

输入输出格式

输入格式：

$N（n<=40000）$ 接下来n-1行边描述管道，按照题目中写的输入接下来是$k$

输出格式：

一行，有多少对点之间的距离小于等于$k$

输入输出样例

题解

假如了解过点分治不难想到做法。

对于这种统计路径并且对于一个点p能分治成过p和不过p的，可以很容易联想到点分治做法。

求出当前树的重心
dfs求出每个点到当前重心的距离，排序后用双指针扫描统计，注意容斥，把重心每个子树在这样做一遍即可
递归每个子树重心（注意，如果递归的点已经被访问，代表已经被处理，返回即可。）

整个做法的时间复杂度是$O(nlog^2n)$

第二步的容斥网上都讲的繁琐玄学。。。然后我就想到这个方法，可能慢一点但很好理解，就代表去掉相同子树里的点对（不属于简单路径）。

还有就是为什么递归重心最多只需要$logn$次，给出证明：

这个命题等价于将重心删除后，最大联通块小于等于树大小的一半，这里我们可以反证。

如果最大联通块的大小超过一半，那么其它的加起来小于一半，此时重心取那个最大联通块与当前重心相连的点时比当前重心优，即当前重心不满足重心定义，与初始条件矛盾。所以

最大联通块小于等于树大小的一半。

然后就没什么了。

考虑点分治奇多无比的细节与今天阴暗的内心世界，我决定咕掉代码。

树的经典问题和方法

路经统计
欧拉序列
树的动态查询问题
轻重路径剖分

第一个标题即树分治算法，略过，最后一个标题仅仅复习一些重要性质的证明。

欧拉序列

DFS一颗树不管刚访问还是回溯都把这个点加进欧拉序列，然后在这个序列上可以做很多有趣的事情，比起树链剖分这个似乎简单一些。

动态查询问题

改单边或单点查询也是单边或单点使用欧拉序列+树状数组即可，否则HPD解决一切。

轻重路径划分

简单叙述原理以及对时间复杂度的论述:

原理就是将树划分成重链轻链，然后通过适当的编号将重链接成序列用线段树维护，而由重儿子和轻儿子的定义可知，对于节点u的轻儿子v，

$sz[v]<=\frac{1}{2}sz[u]$

，这还是最最坏的情况下（均摊来讲要小得多）,最基本的放缩。

所以由这个显而易见的结论，我们还知道：

对于按轻重边划分有如下两条性质：

1.对于轻边$(u,v)$，

$size(v)<=size(u)/2$

2.对于从根到某一点的路径，轻边数不超过

$O(logn)$

重链数不超过

$O(logn)$

对性质1进行证明：

设$u$有$k$个子节点，分别为

$v1,v2,...，vk$

设

$(u,v1)$

为重边，则其余

$(u,vi)(i>1)$

为轻边。

$size(u)=size(v1)+size(v2)+...+size(vk)+1$

(其中k>=2，因为若k=1,则该边必为重边，即不含轻边)

$size(v1)>=size(vi)(i>1)$ $size(vi)+size(vi)=2∗size(vi)<=size(vi)+size(v1)<=size(u)$

即

$size(vi)<=size(u)/2$

对性质2进行证明:

设从$root$到$v$的路径中有k条轻边:

$root−>v1−>v2−>vk−>vroot−>...−>v1−>...−>v2−>...−>vk−>...−>v$

(其中

$−>v1,−>v2,...,−>vk−>v1,−>v2,...,−>vk$

为轻边)

$size(vk)>=size(v)>=1$ $size(vk的前趋)>=2∗size(vk)(性质1)>=2$

同理可得：

$size(vk−1的前趋)>=2∗size(vk的前趋)>=22size(vk−1的前趋)>=2∗size(vk的前趋)>=2^2$

所以有：

$n=size(root)>=size(v1的前趋)>=2kn=size(root)>=size(v1的前趋)>=2^k$

所以

$k=O(logn)$

从root到v的路径中有k条轻边，那么路径上其他边即为重边，那么重链数=k+1，所以重链$O(logn)$。

从上面的阐述中我们也可以理解到为什么树链剖分的常数那么小，因为很显然每一步放缩都是在2个节点并且是在轻重儿子最接近的情况下得出的结论。

我自己抄自己，是不是和CCF一样牛逼？

就到这里吧，滚回去学文化课。