点分治学习笔记

点分治

点分治是一种处理树上路径问题的常见方法。

先引入例题。

求树上有多少条路径的长度是 3 的倍数。

点分治的过程是每次找到当前联通块的重心，然后处理所有跨过重心的路径，然后删去重心，递归每个子树再进行处理。

根据重心的性质，重心的每个儿子的子树大小都不超过 \(\dfrac{n}{2}\)，因此每递归一次大小就减半，于是每个点只会被考虑 \(O(\log n)\) 次。容易发现，每条路径都会被不重不漏地考虑到。

具体的，假设当前枚举的重心为 \(x\)，我们对 \(x\) 的每个子树进行 dfs，求出每个点到 \(x\) 的距离（以下距离都对 3 取模），同时记录下来每个距离有多少点，这就是以 \(x\) 为一端的路径的共线。再考虑其他点的贡献。对于一个子树 \(y\)，我们先进行一遍 dfs 把自己的贡献去掉，然后再进行一遍 dfs，此时统计的答案就是正确的了。

点分治本身的常数较大。

边分治

边分治和点分治类似，点分治的过程是每次找到重心，边分治则是找到一条边使得两端的子树中较大的最小。

容易发现直接边分治可以被菊花图卡掉，我们每次选择一条边后剩下的联通块大小还是 \(O(n)\) 的。这时就需要三度化，就是说我们新建一些虚点和虚边，使得任意两个实点之间的距离不变的情况下每个点的度数不超过 3，这样复杂度就是正确的了。

边分治更适合处理一些不方便减掉贡献的问题。在点分治的过程中，我们需要去掉当前子树的贡献再计算答案，但是边分治每次只有两个子树，可以先 dfs 一边的子树，求出另一边的答案，再反过来处理一次。

我们通过一道题来发现边分治的优势。

给定两棵树，点有点权 \(A_x\)，第一棵树有边权，记 \(dis(u,v)\) 为第一棵树上两点的距离，定义路径 \(P(u\rightarrow v)\) 为第二棵树上 \(u\) 到 \(v\) 的简单路径上的点，记 \(sub_x\) 为第二棵树上 \(x\) 的子树，对于每个点 \(x\)，求出 \(\max\limits_{y\in sub_x}dis(u,v)+\sum A_{P(v\rightarrow u)_i}(i-1)\)

如果采用点分治，我们建出当前联通块的点在第二棵树上的虚树后，需要实时维护根的子树个数棵李超树，这样复杂度就假了。

因此只能采用边分治，每次只有两个子树，就只用维护两棵李超树，复杂度就是正确的。

点分树

点分树就是把点分治的过程离线下来，每个点在点分树上的父亲就是点分治过程中上一层的重心，因此有很好的性质，比如深度是 \(O(\log n)\) 的，子树大小和是 \(O(n\log n)\) 的。

再点分树上，两点间的距离和原树上大不相同，但是两点在点分树上的 LCA 一定是原树上两点路径上的点，这就意味着我们计算两点的距离还是可以通过 LCA 中转。

P6329 【模板】点分树 | 震波

题意：一棵树，有点权，带修，求到一个点距离不超过 \(k\) 的点的点权和。

思路：这道题要求 \(\sum\limits_{dis(x,y)\le k}a_y\)，那么就枚举 LCA，于是有 \(dis(x,y)=dis(x,z)+dis(y,z)\)，因此 \(ans=\sum\limits_{dis(x,z)+dis(z,y)\le k\&\&LCA(x,y)=z}a_y=\sum\limits_{dis(z,y)\le-dis(x,z) k\&\&LCA(x,y)=z}a_y\)，发现这就是 \(z\) 子树里到 \(z\) 距离不超过 \(k-dis(x,z)\) 的点的点权和减去 \(z\) 往 \(x\) 方向的儿子的子树的答案，于是我们用数据结构维护所有 \(dis(x,z)=i\) 的 \(a_x\) 之和，同时我们还要对每个 \(z\) 维护子树内到 \(fa_z\) 距离为 \(i\) 的点权和，这样就行了。

数据结构可以就用树状数组。

P6626 [省选联考 2020 B 卷] 消息传递

题意：多次询问距离 \(x\) 为 \(k\) 的点数。

思路：离线下来，在点分治的统计答案时处理一个点的所有询问就可以了。因为每个点只会被访问 \(O(\log n)\) 次，复杂度就是 \(O((n+m)\log n)\)。

P4183 [USACO18JAN] Cow at Large P

题意：贝茜被农民们逼进了一个偏僻的农场。农场可视为一棵有 \(N\) 个结点的树，结点分别编号为 \(1,2,\ldots, N\) 。每个叶子结点都是出入口。开始时，每个出入口都可以放一个农民（也可以不放）。每个时刻，贝茜和农民都可以移动到相邻的一个结点。如果某一时刻农民与贝茜相遇了（在边上或点上均算），则贝茜将被抓住。抓捕过程中，农民们与贝茜均知道对方在哪个结点。问对于结点 \(i\,(1\le i\le N)\) ，如果开始时贝茜在该结点，最少有多少农民，她才会被抓住。

思路：大概想到了一半？

首先，一个农民肯定是在它的深度一半的位置堵住贝茜，那么考虑每个堵住贝茜的位置，设 \(g_x\) 表示点 \(x\) 到子树内最近的叶子的距离，那么如果 \(dep_x\ge g_x\)，这个点就可以堵住贝茜。那么什么情况必须要这个点的子树里有农夫呢？就是当 \(dep_{fa_x}<g_{fa_x}\) 时，在 \(x\) 的子树内就必须有一个农夫。这样我们就可以 \(O(n^2)\) 算出答案了。

考虑怎么优化。对于一棵有 1 的贡献的子树，一定有 \(dep_x\ge g_x\)，但是这么多点只产生 1 的贡献，我们发现有 \(\sum deg_i=2\times siz-1\)，即 \(\sum(2-deg_i)=1\)，那么我们让每个满足条件的点都造成 \(2-deg_i\) 的贡献，所有点的贡献和就是答案了。因此答案可以写成 \(ans(x)=\sum\limits_i[dis(x,i)\ge g_i](2-deg_i)\)，就不难用点分治来做了。复杂度 \(O(n\log^2n)\)。（其实到这一步我的第一反应是点分树）。