点分治

解决的问题

常用于解决树上大规模的路径问题。

基本思想

由于树上所有的路径都可以转化为经过重心的路径和没有经过重心的路径，对于前者可以直接 $O(n)$ 处理，对于后者则可以递归子树处理。

时间复杂度是 $O(n \log n)$。

算法步骤

1. 寻找树的重心，将其作为根。
2. 求出所有端点是根的路径。
3. 求解问题，并递归子树回到第一步。

细节

找重心细节

正确的找重心是复杂度得到保证的必要条件，若出现 TLE 问题应当首先查看 size 的处理是否正确，以及重心找对没有。

以及不要忘记 vis 数组，不能重复递归已经处理过的根。

void groot(int x, int fa, int sum) {
    si[x] = 1; mx[x] = 0;
    for(auto i : G[x]) {
        int to = i[0];
        if(to == fa || vis[to]) continue;
        groot(to, x, sum);
        si[x] += si[to];
        mx[x] = max(mx[x], si[to]);
    }
    mx[x] = max(mx[x], sum - si[x]);
    if(mx[x] < mx[rt]) rt = x;
}

递归处理细节

当处理完根节点的答案之后，应当递归处理子树的重心，在这之前先要再找一次子树的重心。并且把重心作为子树的根节点

void dfs(int x) {
    vis[x] = 1; ans += work(x, 0);
    for(auto i: G[x]) {
        int to = i[0] ;
        if(vis[to]) continue;
        ans -= work(to, i[1]);
        mx[0] = n, rt = 0; 
        groot(to, x, si[to]);   // 找重心。
        dfs(rt);                // 不要忘记拿重心当作子树的根。
    }
}

例题

P4183 [USACO18JAN] Cow at Large P

考虑一个节点 $u$ 如果能够拦截贝茜，那么 $dis(root, u) \ge \min(u)$，其中 $\min(u)$ 的定义为离 $u$ 最近的叶子节点。

给出一种计算贡献的方案，对于满足上述条件的节点 $u$，那么它会产生 $1 – child(u)$ 的贡献，其中 $child(u)$ 的定义为 $u$ 的儿子数量，考虑到如果节点 $u$ 成立，那么以节点 $u$ 作为根节点的子树一定也成立，此处的贡献就很巧妙的删除了字数内产生的贡献，可以画图帮助思考。

整理可得，当非根节点 $root$ 为根时，答案为：

$$\sum_{u}[dis(root, u) \ge \min(u)](2 – \deg(u))$$

可以使用点分治求解。

可以在点分治的时候使用树状数组，定义 $d(i)$ 为 $i$ 到重心的距离，我们原本有 $dis(x, i) \ge \min(i)$ 可以转化为 $d(x) + d(i) \ge \min(i)$ 还可以转化为 $d(x) \ge \min(i) – d(i)$，此时已经满足用树状数组处理的条件。

点分树

解决的问题

点分数是点分治的进一步运用，点分数可以对树进行重构使树的层数稳定 $\log n$ 的一种重构树，可以解决与原树形态无关的待修改问题。

基本思想

通过点分治找中心，将每次找到的重心与上一层缔结父子关系，重构完成了。

启发式合并

解决的问题

可以解决一些树上离线不带修询问，且可以合并子树的问题。

基本思想

考虑将树轻重链剖分，利用启发式合并的思想，可以得到较优的时间复杂度。

算法过程

1. 对树进行轻重链剖分。
2. 递归轻子树，记录答案，但不影响全局。
3. 递归重子树，记录答案，全局更改。
4. 重新递归轻子树，合并所有子树答案，并返回上一层。