假设有一个包含 \(N\) 个节点的树，要求“树上距离等于 \(K\) 的点对（路径）有多少个？”。
暴力做法枚举任意两个点，然后算它们之间的距离。总共有 \(O(N^2)\) 条路径，时间复杂度是 \(O(N^2)\)。当 \(N=10^5\) 时，直接超时。而点分治算法可以将时间复杂度优化到 \(O(N \log N)\)，极其高效。
树的路径有一个绝妙的数学性质：如果任意选择一个点 \(u\) 作为“根节点”，那么树上的任意一条路径，必然要么是经过点 \(u\) 的路径，要么是不经过点 \(u\) 的路径（也就是说，这条路径完全包含在 \(u\) 的某一个子树内）。
基于这个性质，点分治的算法步骤非常清晰：
如果在分治时，每次都随意挑一个点当根，万一这棵树是一条链，而每次都挑链的端点，那么每次删掉根节点后，剩下的子树只减少了 1 个节点。这样分治就会退化，复杂度重新变成 \(O(N^2)\)。
为了保证每次切分都能把树“均匀”地切开，考虑树的重心（如果在树中删掉该节点，剩下所有子树中，节点数最多的那棵子树的节点数最小，简而言之，重心就是树的“平衡中心”）。删掉树的重心后，分裂出来的所有子树，每棵子树的节点数量绝对不会超过原树总节点树的一半（即 \(\le \dfrac{N}{2}\)）。由于每次子树规模至少减半，整个分治的递归深度绝对不会超过 \(O(\log N)\) 层。这就是为什么点分治时间复杂度能达到 \(O(N \log N)\) 的原因。因此，点分治也经常被称为重心分治。
可以把点分治的执行过程总结为：
点分治的本质就是利用“树的重心”将树均匀拆分，通过 \(O(\log N)\) 层的局部路径统计，最终组合出全局的解。它非常适合处理“树上路径长度等于/小于 \(K\)”、“路径权值最大/最小”等不涉及动态修改的树上静态统计问题。
给定一棵有 \(n \ (1 \le n \le 10^4)\) 个节点的带权无根树（边权 \(1 \le w \le 10^4\)），进行 \(m \ (1 \le m \le 100)\) 次询问。每次询问给出一个距离 \(k \ (1 \le k \le 10^7)\)，问树上是否存在距离为 \(k\) 的点对。
对于本题，如何高效地求出所有“经过当前重心且长度为 \(k\)”的路径？
要找两个节点 \(x,y\) 使得它们到重心 \(r\) 的距离之和满足 \(\text{dis}(x,r) + \text{dis}(y,r) = k\)。为了防止 \(x\) 和 \(y\) 属于重心 \(r\) 的同一个直接子节点的子树（如果它们在同一个子树中，由于路径必须通过重心 \(r\)，则它们在拼合时会经过重复的边，是不合法的），采用逐步合并的思想。
因为 \(k \le 10^7\)，桶数组很大。如果每次处理完一个重心后都清空整个数组，单次清空的时间复杂度将是 \(O(k)\)，会导致超时。在讲距离存入桶中时，记录所有被修改过的位置。在处理完当前重心的所有子树后，只循环遍历改过的部分，将对应的桶重置。这样每次清空的时间复杂度仅与当前子树的大小呈线性关系，非常高效。
在点分治中，递归深度为 \(O(\log n)\) 层，在每一层分治中，需要对所有节点进行一次 DFS 求解距离，并对 \(m\) 个询问进行 \(O(1)\) 的查桶匹配，因此总时间复杂度为 \(O(m \cdot n \log n)\)。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e4 + 5;
const int M = 105;
const int K = 1e7 + 5;
struct Edge {
int to, w;
};
vector<Edge> g[N];
vector<int> tmp, dis;
int n, m, q[M], maxp[N], sz[N], sum, root;
bool vis[N], flag[K], ans[M];
void centroid(int u, int f) { // 寻找当前子树的重心
sz[u] = 1;
maxp[u] = 0;
for (Edge e : g[u]) {
int v = e.to;
if (v == f || vis[v]) continue;
centroid(v, u);
sz[u] += sz[v];
maxp[u] = max(maxp[u], sz[v]); // 找出最大子树大小
}
maxp[u] = max(maxp[u], sum - sz[u]); // 还要考虑向上走的那一部分连通块的大小
if (maxp[u] < maxp[root]) root = u; // 选择最大子树最小的节点作为重心
}
void distance(int u, int f, int d) { // DFS 获取当前子树中所有节点到重心的距离
if (d >= K) return;
dis.push_back(d);
for (Edge e : g[u]) {
int v = e.to, w = e.w;
if (v == f || vis[v]) continue;
distance(v, u, d + w);
}
}
void solve(int u) { // 分治处理以 u 为重心的子树
vis[u] = true; // 标记该重心已被处理，相当于在树中“删除”此节点
flag[0] = true; // 重心到自身的距离为 0
tmp.clear();
tmp.push_back(0); // 记录修改过的桶位置
for (Edge e : g[u]) { // 遍历重心的每一个子树
int v = e.to, w = e.w;
if (vis[v]) continue;
dis.clear();
distance(v, u, w); // 获取当前子树内所有节点到重心的距离
// 尝试将当前子树中的距离与之前其他子树中已保存的距离进行配对
for (int d : dis) {
for (int i = 1; i <= m; i++) {
if (q[i] >= d && flag[q[i] - d]) ans[i] = true;
}
}
// 将当前子树的距离加入到桶中，以便后面的子树进行配对
for (int d : dis) {
if (!flag[d]) {
flag[d] = true;
tmp.push_back(d); // 记录修改过的位置
}
}
}
for (int x : tmp) flag[x] = false; // 快速清空桶，只清空修改过的位置
// 递归处理子树，继续进行点分治
for (Edge e : g[u]) {
int v = e.to;
if (vis[v]) continue;
sum = sz[v]; // 设定子树的总大小
root = 0;
maxp[0] = n;
centroid(v, 0); // 在子树中寻找新的重心
solve(root); // 递归求解
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back({v, w});
g[v].push_back({u, w});
}
for (int i = 1; i <= m; i++) scanf("%d", &q[i]);
maxp[0] = n; sum = n; root = 0;
centroid(1, 0); // 寻找整棵树的重心
solve(root); // 从整棵树的重心开始进行点分治
for (int i = 1; i <= m; i++) {
if (ans[i]) printf("AYE\n");
else printf("NAY\n");
}
return 0;
}
给定一棵有 \(n \ (1 \le n \le 4 \times 10^4)\) 个节点的树，每条边有边权（\(0 \le w \le 10^3\)），求树上两点距离小于等于 \(k \ (0 \le k \le 2 \times 10^4)\) 的点对数量。
使用点分治算法对于当前树，将其分成三种路径：
根据容斥原理，可以将第 1 类和第 2 类路径统一看待，即“所有在以 \(u\) 为重心的连通块中，经过 \(u\) 且长度 \(\le k\) 的简单路径”，其数量等于以 \(u\) 为重心的子树中所有节点两两拼合路径 \(\le k\) 的点对数 减去 每一棵子树 \(v\) 中所有节点两两拼合路径 \(\le k\) 的点对数。通过减去在同一个直接子树内配对的非法路径（因为这些路径并没有真正通过重心 \(u\) 且包含了重复的树边），就可以准确得到经过重心 \(u\) 的合法路径总数。
对于以重心 \(u\) 为根的子树，通过 DFS 遍历当前连通块，将其中的节点到 \(u\) 的路径距离收集到数组 \(d\) 中。在收集好距离数组后，以 \(u\) 为重心的子树中所有节点两两拼合路径 \(\le k\) 的点对数实际上就是去求有多少对元素 \(x,y\) 满足 \(d_x + d_y \le k\)。对 \(d\) 数组进行排序，可以使用双指针算法控制窗口 \([l,r]\)，如果当前 \(d_l + d_r \le k\)，由于数组已排序，那么对于固定的左端点 \(l\)，右端点从 \(l+1\) 到 \(r\) 之间的所有数与 \(d_l\) 相加都一定 \(\le k\)，所以可以直接把这部分的点对数 \(r-l\) 累加到局部的答案中，并让左端点右移；如果 \(d_l + d_r \gt k\)，说明当前的右端点太大了，必须将右端点左移以寻找更小的组合。
点分治的递归深度为 \(O(\log n)\) 层，每一层分治中，所有节点都会被参与到一次距离计算和排序中。因此，总时间复杂度为 \(O(n \log^2 n)\)。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 4e4 + 5;
struct Edge {
int to, w;
};
vector<Edge> g[N];
int k, sum, root, maxp[N], sz[N], ans;
bool vis[N];
vector<int> dis;
void centroid(int u, int f) {
sz[u] = 1; maxp[u] = 0;
for (Edge e : g[u]) {
int v = e.to;
if (v == f || vis[v]) continue;
centroid(v, u);
sz[u] += sz[v];
maxp[u] = max(maxp[u], sz[v]);
}
maxp[u] = max(maxp[u], sum - sz[u]);
if (maxp[u] < maxp[root]) root = u;
}
void distance(int u, int f, int d) {
dis.push_back(d);
for (Edge e : g[u]) {
int v = e.to;
if (v == f || vis[v]) continue;
distance(v, u, d + e.w);
}
}
int count(int u, int d) {
dis.clear();
distance(u, 0, d);
sort(dis.begin(), dis.end());
int res = 0, l = 0, r = dis.size() - 1;
while (l < r) {
if (dis[l] + dis[r] <= k) {
res += r - l;
l++;
} else {
r--;
}
}
return res;
}
void solve(int u) {
ans += count(u, 0);
vis[u] = true;
for (Edge e : g[u]) {
int v = e.to;
if (vis[v]) continue;
ans -= count(v, e.w);
sum = sz[v];
root = 0;
maxp[0] = sum;
centroid(v, 0);
solve(root);
}
}
int main()
{
int n; scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back({v, w});
g[v].push_back({u, w});
}
scanf("%d", &k);
sum = n; root = 0; maxp[0] = n;
centroid(1, 0);
solve(root);
printf("%d\n", ans);
return 0;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。