点分治

好像边分治没什么用，所以不写了。

0.定义#

点分治，说白了就是优化过的暴力 /

主要来解决和树上路径有关的问题，比如长度为 $k$ 的路径数量。

时刻记住，点分治是在无根树上跑的，并且是静态的。

1.过程#

我们首先先指定一个点 $p$ 为根，称作分治中心。

我们考虑两种路径：

1. 经过 $p$ 的路径
2. 不经过 $p$ 的路径

第二种路径是一个子问题，直接向下递归。我们着重看第一种路径。

我们可以先预处理所有点到 $p$ 的距离 $dis _ u$，则经过 $p$ 的路径可以由两个不属于同一子树的点的 $dis$ 拼起来得到。

一般处理这种的方式有先查询再加入，应用容斥原理等。难点就在怎么用 DS 快速维护第一种路径上。

2.点分树#

我们看这样一个问题

1. 求与 $x$ 的距离 $\le k$ 的点的点权和
2. 修改一个点的点权

如果不看修改，那这就是一个点分治题。所以暴力就是每次查询直接做一次点分治。

我们发现点分治的时间开销主要在寻找重心上，那我们可以把每一次的重心记录下来，重构一棵树，这样就节约了很多的时间。

然后这就是点分树的定义，把每次的分治中心连起来，构建一棵树。

性质#

1. 深度等同于点分治的深度，即 $\Omicron(\log n)$，因此可以在上面跑一些平常会 T 的暴力。
2. $x,y$ 在点分树上的 LCA 一定在原树上 $x,y$ 的路径上，即 $dis(x,y) = dis(x,LCA) + dis(LCA,y)$。

回到刚刚那个题上，我们可以考虑暴力跳父亲，跳到根为止来枚举路径。

但是，我们可能会统计到在同一子树内的答案，于是我们还需要用容斥原理去重。

我们可以记录 $sum _ 1(x,k)$ 表示在重构树上与 $x$ 的距离 $\le k$ 的点权和，$sum _ 2(x,k)$ 表示重构树上 $x$ 的父亲的子树中与其距离 $\le k$ 的点权和。

则答案为 $\sum sum _ 1(fa _ x,k - dis) - sum _ 2(x,k - dis)$。

修改就一路向上跳单点修改就好，因此我们可以直接用树状数组维护。

3.总结#

点分治的主要难点就在如何维护你需要的路径的信息，本身其实并不难。

后面需要的时候我可能会补一个边分治/边分树。

欸这个边分树还能可持久化？