【学习笔记】点分治

xuyunao · 2026-01-09 21:28:12 · 算法·理论

点分治

点分治从小白到入门？

Update on 2026.1.10：增加了对点分树及点分治性质的补充，并增加了前言后记部分内容。
Update on 2026.1.10：添加了树上均衡路径一题，辛苦管理审核。

前言

我常常追忆过去。

​ ——《追忆》

抬头啊 星空竟是陌生的眼睛
河流啊 带走我被抹去的乳名
有人啊 寻找我眼角的胎记
寻找 候鸟的踪迹

​ ——非弹力碰撞《小孩》

自从 NOIP 之后就一直没有找到一个好的竞技状态，T2 没判相等错失两倍线，虽然当时就已经接受了结果，但是终究还没有调整好，省选模拟赛也没有切出来过题，很摆。与其这样，不如找点事情干，调整一下，尽快找回状态。

在 LCA 课上实在听不懂串串了，找点事情做，想起来当时首都 这题，于是想着把自己做过的一些比较好玩的点分治记录一下，刚好复习一下，语言应该不会很专业很官方，多数是结合自己理解的通俗语言。

什么是点分治

点分治是一种树分治，能解决的是树上路径问题，以我目前的知识水平，只会用点分治解决不定根的问题，更确切来说，点分治无法简单维护祖先关系，因此它不能处理依赖祖先关系的问题。

举个非常抽象的例子（这东西我还真的思考过），你要在一棵 trie 上点分治，但很快就发现这显然是不行的，因为 trie 维护字符串信息，它字符串是有序的，如果进行点分治会使得串的顺序被打乱。可能不那么好理解，后面遇到了自己思考一下就知道为什么不行了。

点分治怎么解决路径问题的

点分治是一个递归分治的过程，简述一下，可以分为下面步骤：

• 找到当前连通块重心，以它作为分治中心
• 递归进入分治中心，统计经过分治中心的路径信息
• 分治中心将当前连通块又划分为若干子连通块，我们对子连通块递归进行上述操作。

由于重心具有良好的性质，最大子树大小不超过 \frac{n}{2}，也就是说，我们每递归一层，这个子连通块大小就会减半，因此递归层数为 O(\log n)。由于递归层数有了保证，我们就可以每次从分治中心出发，暴力枚举当前连通块内每个点并统计信息。

分析点分治的时间复杂度，大致可以表示为递归层数 \times 处理每层信息的时间复杂度，递归层数为 O(\log n)，处理每层信息就要看具体使用的数据结构，比如线段树或排序就是 O(siz \log siz)，总复杂度就是两个乘在一起。

这里要注意，子连通块处理信息需要的复杂度一定是与 siz 有关而不是 n。举个例子，如果你要对子连通块维护值域线段树，那么就需要离散化之后处理，这样才是 O(siz \log siz)，要不然每次变成 O(n \log n)，总复杂度变成 O(n^2 \log ^2 n)，总之点分治处理、清空、维护信息都只能是依赖于当前分治中心的 siz 的。

另外，如果我们把点分治每一层重心向上一层中心连边，这样就会形成一棵树的结构，我们称之为点分树，点分树具有很多优秀的性质：

• 点分树深度为 O(\log n)，这意味着我们可以支持暴力枚举祖先。
• 我们定义 siz_u 为点分树上 u 的子树大小，则 \sum siz_u 为 O(n\log n) 级别，不妨考虑对每个点算贡献，每个点的贡献就是祖先数量，而点分树有 O(\log n) 层，于是总的量级为 O(n\log n)。
• 继续上面的结论，记每个分治中心所处理的连通块大小为 siz_u，则 \sum siz_u 也是 O(n \log n) 级别，可以参照上面考虑，这个后面 Tree-MST 那题会用到。

一些例题

说完理论的东西，应该都还不太懂吧，所以找一些例题说一下。

P3806 【模板】点分治 - 洛谷

题意

这是点分治的模板题，给定一棵树，询问是否存在长度为 k 的路径，n \le 10^4，q\le 100，k \le 10^7。

Solution

维护路径信息可以使用点分治，考虑每次找到重心 rt 之后，从 rt 开始 dfs 整个连通块，维护 rt 到每个 u 的路径长度，那么对于 rt 子连通块内的两个点 u,v，他们之间的路径长度 dis(u,v) = dis(rt,u) + dis(rt,v)，那么我们维护所有 dis(rt,u)，对每个 u 统计答案，问题变成了给定 x，询问是否存在 k - x，这个是好维护的。

但还有一个需要注意的点，点分治要求每一条路径只在深度最高的分治中心被统计到，因此当我们统计信息时，假设 u,v 均位于 rt 的同一子连通块，则需要在后面的分治中心统计，而不能在当前层统计。简单而言，我们要求在 rt 处被统计到的点对 u,v 必须不在同一棵子树。

如何处理这个东西呢？有两种方法：

1. 考虑先全都统计上，然后减去每个子连通块内，同样条件下产生的贡献。这里要注意同样条件，例如我们维护路径长度，则当我们对一个子连通块 v 去重，我们需要把 dis[v] 初始化成 w(u,v)，也就是我们要在 u 统计答案的情境下，计算 v 子树内产生了多少贡献。
2. 也可以用类似 dsu on tree 的合并方式，我们逐个连通块计算答案，先求出该连通块的信息，然后从之前的数据结构中尝试统计答案，统计完当前子连通块后再把当前子连通块内的贡献全都插入数据结构中。

会处理一个分治中心，剩下的就很好做了，只需要找重心，递归下去做就好了。

这里有若干小细节，是我见过刚开始很容易犯的：

• 找重心需要用到一个 mx 数组表示最大子树大小，我们要初始化一下，通常我是写成 mx[rt = 0] = inf。
• 由于 mx 需要考虑原树子树外的那棵子树，因此我们需要 mx[i] = max(mx[i],tot)，在这里 tot 表示当前子连通块大小。
• 当我们走一个点 v 时，要时刻注意判断 v 是不是没有递归过，我们给已经处理的分治中心打上标记，判断 v 是否被标记。
• 处理当前分治中心，维护信息大小为 siz 而不是 n。
• 记得每次 getroot 的时候清空 mx。

实现

这里给出我的实现（不一定很优）

int mx[maxn],siz[maxn];
bool vis[maxn];
void getroot(int u,int fa)
{
    siz[u] = 1;mx[u] = 0;
    for(auto nx : G[u])
    {
        int v = nx.fi;
        if(v == fa || vis[v]) continue;
        getroot(v,u);
        siz[u] += siz[v];
        mx[u] = max(mx[u],siz[v]);
    }
    mx[u] = max(mx[u],tot - siz[u]);
    if(mx[u] < mx[rt]) rt = u;
}

找重心：要注意每次清空 mx，并且每次给 tot 重新赋值，tot 表示当前子连通块大小，同时注意初始化 rt，我一般写成 mx[rt = 0] = inf。如果 tot 赋值错误，并不会导致正确性有问题，但是可能找到错误的重心，导致时间复杂度退化。

void divide(int u)
{
    vis[u] = 1;
    getans(u);
    for(auto nx : G[u])
    {
        int v = nx.fi,w = nx.se;
        if(vis[v]) continue;
        tot = siz[v];rt = 0;
        getroot(v,u); // 注意这里！！！
        getroot(rt,0);
        divide(rt);
    }
}

divide 分治函数：要注意标记 vis，同时注意打注释的地方，在每次 divide 之前，找完重心都要重新 getroot(rt,0)，否则会得到错误的 siz，也就导致 tot 错误，最终使得时间复杂度退化，例如一条链的情况如果不重新 divide 可能出现问题。

const int V = 1e8 + 10;
bool had[V];
int que[maxn],ed;
int dis[maxn],cnt;
void dfs(int u,int fa,int d)
{
    dis[++cnt] = d;
    for(auto nx : G[u])
    {
        int v = nx.fi,w = nx.se;
        if(vis[v] || v == fa) continue;
        dfs(v,u,d + w);
    }
}
void getans(int u)
{
    had[0] = 1;ed = 0;
    for(auto nx : G[u])
    {
        int v = nx.fi,w = nx.se;
        if(vis[v]) continue;
        cnt = 0;dfs(v,u,w);
        for(int i = 1;i <= cnt;i++) 
            for(int j = 1;j <= m;j++)
                if(q[j] >= dis[i]) ans[j] |= had[q[j] - dis[i]];
        for(int i = 1;i <= cnt;i++) had[dis[i]] = 1,que[++ed] = dis[i];
    }
    for(int i = 1;i <= ed;i++) had[que[i]] = 0;
}

getans 部分：这里给出的是第二种去重方式，也就是每次先算贡献，再插入到数据结构中，避免同一子连通块产生贡献。要注意每次情况都是 O(size) 的，而第一种去重方式由于每次去重都要递归所有子树，会导致常数较大。

请注意，在这篇文章中的代码有一些可能只写了一次 getroot，因此请注意自己修改！！！

针对这题还有一个需要注意的点，边权 w \le 10^4，n \le10^4，路径信息是可能到达 10^8，因此要么开数组开到 10^8，要么在信息超过 10^7 时直接 continue。

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i < n;i++) 
    {
        int u,v,w;cin >> u >> v >> w;
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    for(int i = 1;i <= m;i++) cin >> q[i];
    mx[rt = 0] = inf,tot = n;
    getroot(1,0);
    getroot(rt,0);
    divide(rt);
    for(int i = 1;i <= m;i++) cout << (ans[i] ? "AYE\n" : "NAY\n");
    return 0;
}

最后主函数：要注意的是初始化 rt,mx,tot 以及在 divide 以前进行两次 getroot 从而求出正确的子树大小信息。这里还有一个小细节，我们可以将所有询问全都输入然后在每次分治过程中更新答案。

全部实现

复杂度分析

我们分析一下复杂度，点分治递归层数 O(\log n)，对于每个分治重心，统计答案 O(m \times size)，总复杂度为 O(nm\log n)，但我们要注意，点分治需要递归，常数是非常大的，因此如果我们在每次输入询问后都进行一次点分治，这个大常数是要乘上 m 的，可能会导致被卡常。

P4178 Tree - 洛谷

题意

询问树上长度 \le k 的路径数量，n \le 4 \times 10^4，k \le 2 \times 10^4。

Solution

非常板的一题，考虑像上一题一样，维护从分治中心出发到每个点的路径长度，那么要找 \le k，我们可以直接排序双指针统计答案，这份代码使用的是第一种去重方法，也就是对于子树重新 getroot 并减掉。

代码

CF293E Close Vertices - 洛谷

这题可以说是上一题加强版了。

题意

询问树上边数 \le l 且边权值和 \le w 的路径数量。