P3806 【模板】点分治 1 题解

xuyunao · 2025-05-13 08:40:54 · 题解

P3806 【模板】点分治 1 题解

Update on 2026.1.9： 发现之前大部分的点分治都没有在求重心后重新求出正确的子树大小，并且疑惑了好久，改动在代码中 divide 部分，求出重心后添加了 getroot(rt,0) 用来更新子树大小。

Update on 2026.1.9： 思虑再三重写了，希望管理还能给通过一下，真的尽力在好好写了。

什么是点分治

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

举个非常抽象的例子（这东西我还真的思考过），你要在一棵 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 的。

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

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 的，可能会导致被卡常。