点分治

前言

我常常追忆过去。

​ ——《追忆》

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

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

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

什么是点分治

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

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

• 点分树深度为 $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 【模板】点分治 - 洛谷

题意

Solution

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;
}

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);
    }
}

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;
}

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;
}

复杂度分析

P4178 Tree - 洛谷

题意

Solution

CF293E Close Vertices - 洛谷

题意

Solution

U648884 MX-BJ 树上均衡路径 - 洛谷

题意

Solution

A_zjzj 讲解的模拟赛，正解等下再写，这题点分治其实是歪解，但倒也是正解。

实现

几个需要思考的题

P12491 [集训队互测 2024] 串联 - 洛谷

题意

Solution

P7215 [JOISC 2020] 首都 - 洛谷

题意

Solution

先来简单解释一下，对于没被围起来的部分，说明他们层次更高，在前面已经被处理过了，可以尝试自己这样子画图理解一下，这样的图非常适合点分治（还是从 ez_lcw 课上学到的），不难发现这两个 $y$ 之间路径是在绿色点被统计到的，也没有经过当时分治中心。

AT_cf17_final_j Tree MST - 洛谷

题意

Solution

对于稠密（完全）图 $(V, E)$ 求 MST，可将 $E$ 分成 $E_1, E_2, \dots, E_k$，满足其并集为 $E$，对每个边集求 MST（可以不连通），再将得到的边集再求一次 MST，即为原图的 MST。

P12480 [集训队互测 2024] Classical Counting Problem - 洛谷

题意

• 选择当前树上编号最大或最小的点，删除它以及以它为端点的所有边，并任选一个连通块作为新的树。
• 记 $\min$ 为当前树上编号最小值，$\max$ 为当前树上编号最大值，$size$ 为树上节点数量。定义一棵树的权值为 $\max \times \min \times size$，求能通过上述操作得到的非空树的权值和，答案对 $2^{32}$ 取模。

Solution

• 一个 $\min$ 和一个 $\max$ 能够确定唯一的树。

考虑 $(l,r,x)$ 的关系大概是像下图中这样，按照 ez_lcw 课上讲的名字，称之为 “风车形”。

• 对于每个位置 $i$，$l = i$ 的 $l$ 的编号和 $sum$。
• 对于每个位置 $i$，$mi_x = i$ 的 $x$ 的数量 $cnt$。
• 对于每个位置 $i$，$l = i$ 的合法 $(l,x)$ 对的贡献和 $val$。

• 这个点作为 $x$，此时对于 $l \le mi_x$ 的所有 $l$，$x$ 都能与之配对产生贡献。对于所有合法的 $l$，它能增加的贡献值也为 $l$，要对这些 $l$ 的 $val$ 加上他们对应的 $sum$。同时插入 $x$ 后，$mi_x$ 处的 $cnt$ 也要 $+1$。
• 这个点作为 $l$，此时我们需要计算这个 $l$ 能和多少 $x$ 产生贡献，发现就是询问 $mi_x \ge l$ 的 $x$ 的数量，由于前面我们对每个位置 $i$ 维护了 $mi_x = i$ 的 $x$ 的数量，这里可以直接区间查询，同时 $l$ 位置的编号和也需要增加。

实现细节

• 注意到模数是 $2^{32}$，可以直接使用 unsigned int 存储，这样就不需要取模了。
• 对于每层值域需要离散化，否则每层都是 $O(n\log n)$ 的，总时间复杂度会变成 $O(n^2 \log^2 n)$。
• 要先加入 $l,x$，再询问 $r$。
• 由于需要去重，如果对每棵子树减去贡献，注意路径 $\min$ 和 $\max$ 的初始值。
• 该清空的要清空，该赋值的要赋值。

完整代码

后记

我该在哪里停留？我问我自己。

​ ——《追忆》

有一天 阳光照进冰冷的河里
有一天 藤蔓爬上了云梯
你听啊 让风代替我喊你
知道 你从未放弃

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