点分治

一句话算法

每次在当前连通块里挑一个点当分治中心，把「经过这个中心的路径」在本层当场数掉；剩下的路径必然整条落在某一棵子树里，于是递归进去继续数。中心选重心，才能保证每层规模减半，总层数只有 $O(\log n)$ 。

阅读前建议先掌握 [ Rbook: 树的重心]：点分治的全部效率都来自「重心让每个子问题不超过一半」。分治框架本身只是普通的 DFS，还用到 [ Rbook: DFS序] 里的子树概念。

本文的组织顺序是：先从一道具体题目看出瓶颈在哪，再说明为什么「按路径经过谁分类」能把 $O(n^2)$ 降下来，接着讲清容斥这一步（这是唯一不直观的地方），然后给出可直接复用的模板与两道例题的改造方式，最后集中列出踩坑点。

1 问题引入：一条路径一条路径算是来不及的

以 [ luogu P4178] 为例：给定一棵 $n$ 个点的带权树，求距离不超过 $K$ 的点对数量。 $n\le 4\times 10^4$ ，边权不超过 $10^3$ ， $K\le 2\times 10^4$ 。

最直接的做法是枚举起点，DFS 一遍求出它到所有点的距离：

1
2
3

for 每个起点 s:
    DFS 一次，求 s 到每个点的距离
    统计距离 <= K 的点

一次 DFS 是 $O(n)$ ， $n$ 个起点就是 $O(n^2)$ 。 $n=4\times10^4$ 时约 $1.6\times10^9$ 次操作，过不了。

问题的本质是：答案依赖的量有 $O(n^2)$ 个（点对），但不能一个一个算。 所以必须想办法「一次算出一大批点对的贡献」。点分治给的就是这种批量统计的方式。

2 核心直觉：按「路径经过谁」分类

固定的树上看，任意一条路径都有两种处境。任选一个点 $u$ ：

左边：路径 A–B 经过 u，可在本层统计；右边：路径 C–D 同属一棵子树，与 u 无关

经过 $u$ ：路径被 $u$ 分成两段，长度分别是 $u$ 到两个端点的距离。所以只要知道两侧各点到 $u$ 的距离，就能一次配对统计，不需要知道具体端点是谁。
不经过 $u$ ：这条路径整条都在删除 $u$ 后剩下的某一个连通块（也就是 $u$ 的某一棵子树）里，和 $u$ 无关。

这个分类有两个好性质：

第 ① 类可以批量算——一堆距离两两配对，是排序加双指针的活。
第 ② 类规模变小了——不再包含 $u$ ，可以递归处理。

于是算法有了轮廓：

solve(当前连通块):
    选出中心 u
    统计「经过 u」的路径（批量）
    删掉 u，对每个剩下的连通块递归 solve

3 为什么中心必须选重心

轮廓里有一句含糊的「选出中心 $u$ 」。它决定算法快慢。

假设每次随便挑一个点，比如永远挑编号最小的点。考虑一条链 $1-2-\cdots-n$ ：第一次删掉 $1$ ，剩下 $n-1$ 个点；再删 $2$ ，剩 $n-2$ 个……每层只减少一个点，一共 $n$ 层，每层还要扫一遍整块，退化成 $O(n^2)$ 。

如果选重心，删除后每块大小都不超过一半（见 [ Rbook: 树的重心]）：

\text{下一层每块大小}\le\left\lfloor\frac{m}{2}\right\rfloor\quad(m\text{ 是当前块大小})

于是沿任意一条递归分支，规模每层减半，层数只有 $O(\log n)$ 。

注意

这里要的是一个性质：子问题规模减半。它保证的是层数少，不保证每层工作量小。每层仍然要把该层的所有连通块扫一遍，总共 $O(n)$ 量级——但层数从 $n$ 降到 $\log n$ ，这才是点分治的收益来源。

注意求重心时用的是当前连通块的点数，不是最初的 $n$ 。这是点分治里最常见的错误，后面「易错点」会再强调。

4 统计经过 $u$ 的路径：容斥

现在解决唯一不直观的一步：怎么在 $u$ 处批量数出「经过 $u$ 」的点对。

先把 $u$ 的每棵子树里的点到 $u$ 的距离都收集起来，得到一个距离多重集 $D$ ，注意它包含 $u$ 自己（距离为 $0$ ）。

如果直接在 $D$ 上数「两数之和 $\le K$ 」的点对数，会混进不该算的：同一棵子树里的两个点，它们在 $D$ 里的配对照样满足条件，但真实路径并不经过 $u$ ，而是整条在那棵子树内部。这类点对属于第 ② 类，应该交给递归，不能在这里重复计入。

处理办法是容斥：

先算 u 到整块所有点的距离集合，再对每个儿子扣掉「该子树内部」的那部分

\text{经过 }u\text{ 的点对数} =\underbrace{\text{calc}(u,0)}_{\text{整块}} -\sum_{v\text{ 是 }u\text{ 的儿子}}\underbrace{\text{calc}(v,\,w(u,v))}_{\text{子树 }v\text{ 内部}}

两个 $calc$ 用的是同一套逻辑：收集一批到 $u$ 的距离，数出两两之和 $\le K$ 的对数。区别只在收集范围和距离起点：

调用	收集哪些点	到 $u$ 的距离起点
`calc(u, 0)`	整块（含 $u$ 自己）	$0$
`calc(v, w)`	只有子树 $v$ 内部	$w(u,v)$ ，因为 $v$ 到 $u$ 就已经有这条边的长度

说明

为什么第一步要把 $u$ 自己放进去？

距离 $0$ 放进集合后，「 $u$ 与某个距离为 $d$ 的点」就体现为 $0+d\le K$ ，一对端点里有一个是 $u$ 的路径就被自动数进来了。若漏掉 $u$ ，所有以 $u$ 为一端的路径都会丢。

为什么减去子树时不会有负数结果？

$calc(v,w)$ 数的是子树 $v$ 内部的点对，这些点对在整块那一步里必然也被数过一次（整块包含子树 $v$ ），所以减法是精确的「扣掉多算的部分」，不是凑出来的。

calc 内部就是排序加双指针：把距离升序排好，左指针从最小开始，右指针从最大开始；若两端之和 $\le K$ ，说明左指针和右指针之间的点都能与左指针配对，一次加上 $(r-l)$ 个；否则右指针左移。

5 完整算法步骤

把上面的部分拼起来：

getsz(u, fa):            返回 u 所在连通块的点数，顺便填好 sz
getroot(u, fa):          在连通块里找重心 root（需要 total = 块大小，sz 已填好）

calc(u):                 统计经过 u 的路径
    D = { u 自己, 距离 0 }
    对 u 的每个未删儿子 v: 把 v 子树内各点到 u 的距离加入 D
    ans += 数 D 中两两之和 <= K 的对数
    对 u 的每个未删儿子 v:
        单独收集 v 子树内各点到 u 的距离
        ans -= 数这些距离两两之和 <= K 的对数

solve(u):
    removed[u] = true
    calc(u)
    对 u 的每个未删儿子 v:
        total = getsz(v, u)        // 重算！子树 v 现在是独立连通块
        getroot(v, u)              // 得到新重心
        solve(root)

divide():
    total = getsz(1, 0)
    getroot(1, 0)
    solve(root)

removed[u] 是「作为分治中心被删掉」的标记。所有遍历（求块大小、求重心、收集距离）都要跳过已删的点，这样它们自然被限制在当前连通块内部。

5.1 为什么 `total` 必须在每一层重算

getroot 判定重心时要用 total - sz[u] 表示「父亲方向」的块大小。这个 total 必须是当前连通块的点数。

如果一直沿用最初的 $n$ ，那么在最深层的连通块里，total - sz[u] 会算出一个远大于真实值的「父亲方向」，于是 mx[u] 全部偏大，重心可能被选错，分治就退化了。

更隐蔽的是复用旧的 sz。sz[v] 是在上一次以某个点为根时算出来的，未必等于删除 $u$ 之后 $v$ 那一块的真实大小。所以每进入一棵子树，都要用 getsz 重新算一遍再交给 getroot。

6 模板代码

下面这份模板可以直接过 [ luogu P4178]：

#include <bits/stdc++.h>
using namespace std;

// 点分治（重心分治）通用框架：数出树上距离不超过 K 的点对数量。
// 对应洛谷 P4178 Tree。
// 约定：输入是连通无环的带权树，边权非负，节点编号 1..n。
const int maxn = 200000 + 5;

int n, K;

struct Edge {
    int to; // 边指向的点
    int w;  // 边权
};

vector<Edge> g[maxn];

/*------------------------ 点分治 代码 开始 ------------------------*/
bool removed[maxn]; // removed[u]：u 已被选作分治中心而删掉
int sz[maxn];       // sz[u]：当前连通块内的子树大小（含自己）
int mx[maxn];       // mx[u]：删掉 u 后，当前连通块内最大块的大小
int root, total;    // 当前连通块的重心、当前连通块的总点数

int dis[maxn], cnt; // 收集到的"到分治中心的距离"

long long ans; // 点对数量，可能是 O(n^2) 级，用 long long

void init(int node_count) {
    n = node_count;
    for (int u = 1; u <= n; ++u) g[u].clear();
    fill(removed, removed + n + 1, false);
    ans = 0;
}

void add_edge(int u, int v, int w) {
    g[u].push_back({v, w});
    g[v].push_back({u, w});
}

// 返回 u 所在连通块（不含已删点）的点数，顺带把 sz 填好。
// 每次递归进子树前都要重新算，不能沿用上一次的 sz：
// 上一次的 sz 是相对另一个根算的，不是这个连通块的大小。
int getsz(int u, int father) {
    sz[u] = 1;
    for (const Edge &e : g[u]) {
        int v = e.to;
        if (v == father || removed[v]) continue;
        sz[u] += getsz(v, u);
    }
    return sz[u];
}

// 在 u 所在连通块里找重心。调用前必须已经用 getsz 填好 sz，
// 且 total 等于这个连通块的真实点数。
void getroot(int u, int father) {
    mx[u] = 0;
    for (const Edge &e : g[u]) {
        int v = e.to;
        if (v == father || removed[v]) continue;
        getroot(v, u);
        mx[u] = max(mx[u], sz[v]); // 儿子方向
    }
    mx[u] = max(mx[u], total - sz[u]); // 父亲方向，别忘了
    if (mx[u] < mx[root]) root = u;
}

// 收集 u 的子树内所有点到"分治中心"的距离，d 是 u 到中心的已有距离。
void getdis(int u, int father, int d) {
    dis[++cnt] = d;
    for (const Edge &e : g[u]) {
        int v = e.to;
        if (v == father || removed[v]) continue;
        getdis(v, u, d + e.w);
    }
}

// 数出 dis[1..cnt] 中"距离之和 <= K"的点对数。
// 双指针要求有序，所以先排序：这一步就是点分治常见的那只 log。
long long count_le() {
    sort(dis + 1, dis + cnt + 1);
    long long res = 0;
    int l = 1, r = cnt;
    while (l < r) {
        if (dis[l] + dis[r] <= K) {
            res += r - l; // l 与 (l, r] 中每个点都能配对
            ++l;
        }
        else {
            --r;
        }
    }
    return res;
}

// 统计跨过 u 的路径：先算整个连通块，再减掉每棵子树内部的部分。
void calc(int u) {
    // 1. 整个连通块的点到 u 的距离（含 u 自己，距离 0）
    cnt = 0;
    dis[++cnt] = 0;
    for (const Edge &e : g[u]) {
        int v = e.to;
        if (removed[v]) continue;
        getdis(v, u, e.w);
    }
    ans += count_le();

    // 2. 减掉同一棵子树内部被重复统计的点对：它们的路径不经过 u
    for (const Edge &e : g[u]) {
        int v = e.to;
        if (removed[v]) continue;
        cnt = 0;
        getdis(v, u, e.w);
        ans -= count_le();
    }
}

void solve(int u) {
    removed[u] = true; // 删掉 u，连通块被切开
    calc(u);           // 处理"经过 u"的路径

    for (const Edge &e : g[u]) {
        int v = e.to;
        if (removed[v]) continue;
        total = getsz(v, u); // 子树 v 现在是独立连通块，大小要重算
        root = 0;
        mx[0] = total + 1; // 哨兵：保证第一次比较一定能更新 root
        getroot(v, u);
        solve(root); // 递归处理剩余连通块
    }
}

void divide() {
    total = getsz(1, 0);
    root = 0;
    mx[0] = total + 1;
    getroot(1, 0);
    solve(root);
}
/*------------------------ 点分治 代码 结束 ------------------------*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    init(n);
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }
    cin >> K;

    divide();

    cout << ans << '\n';
    return 0;
}

一份实现里 calc 是核心，其余都是脚手架。想改成别的题，通常只需要动 calc 里的「数点对」那一步。

6.1 从「不超过 $K$ 」改成「恰好 $K$ 」

两者可以互相转化，用一次减法即可：

\text{恰好 }=K\text{ 的点对数}=\text{不超过 }K\text{ 的点对数}-\text{不超过 }(K-1)\text{ 的点对数}

因为容斥是线性可加的，对两个不同的阈值各算一遍再相减，结果仍然是「经过 $u$ 且恰好 $K$ 」的点对数。多询问时把两个阈值都算出来即可，不必改容斥结构。

7 另一种统计方式：边收集边标记

容斥不是唯一选择。下面这道题会把差别暴露出来。

[ luogu P3806]

给一棵 $n\le 10^4$ 个点的树，边权 $w\le 10^4$ ，再给 $m\le 100$ 个询问 $k\le 10^7$ ，问每个 $k$ 是否存在距离恰好为 $k$ 的点对。输出 AYE 表示存在，NAY 表示不存在。

如果照搬容斥：每个询问都要跑两遍排序与双指针， $m=100$ 时约 $100$ 倍开销；更麻烦的是「存在性」不是可加的量，直接对布尔值做容斥是错的（必须先数出对数再判断是否大于 $0$ ）。

换个思路：不收集完再算，而是边收集边标记。维护一个桶 used[d]，表示「距离 $d$ 是否已经被占用」。处理 $u$ 时：

used[0] = 本层时间戳        // u 自己
对 u 的每个未删儿子 v:
    收集 v 子树内各点到 u 的距离
    ① 先查询：对每个距离 d 与每个询问 k，看 used[k - d] 是否已被占用
    ② 再标记：把本子树的这些距离写进 used

顺序是 ①→②，绝不能反。先查后标意味着本子树去和「已经处理过的兄弟子树 + $u$ 自己」配对；同一子树内部的两个点这时还没进桶，自然不会被配上。容斥要解决的问题，被处理顺序直接消掉了。

代价是 $(k-d)$ 直接当下标，桶需要覆盖到最大的询问值。

#include <bits/stdc++.h>
using namespace std;

// 点分治：多次询问"是否存在距离恰好为 K 的点对"。对应洛谷 P3806。
// 与 point_divide.cpp 的区别只在一处：统计方式不同。
//   point_divide.cpp  先收集后排序，用容斥"整块减子树"，数点对个数；
//   本文件            边收集边标记，用一个带时间戳的桶，天然不需要容斥。
// 约定：连通无环带权树，边权非负，节点编号 1..n。
const int maxn = 100000 + 5;

int n, m;

struct Edge {
    int to; // 边指向的点
    int w;  // 边权
};

vector<Edge> g[maxn];

/*------------------------ 点分治（多询问） 代码 开始 ------------------------*/
bool removed[maxn];
int sz[maxn];
int mx[maxn];
int root, total;

int dis[maxn], cnt; // 当前子树内各点到分治中心的距离

vector<int> qs;   // m 个询问的 K
vector<char> ok;  // ok[i]：第 i 个询问是否已有答案
vector<int> used; // used[d] == stamp 表示"距离 d 已被占用"
int stamp;        // 时间戳，用来免掉 memset
int maxk;         // 询问里最大的 K，决定桶的大小

void init(int node_count) {
    n = node_count;
    for (int u = 1; u <= n; ++u) g[u].clear();
    fill(removed, removed + n + 1, false);
}

void add_edge(int u, int v, int w) {
    g[u].push_back({v, w});
    g[v].push_back({u, w});
}

int getsz(int u, int father) {
    sz[u] = 1;
    for (const Edge &e : g[u]) {
        int v = e.to;
        if (v == father || removed[v]) continue;
        sz[u] += getsz(v, u);
    }
    return sz[u];
}

void getroot(int u, int father) {
    mx[u] = 0;
    for (const Edge &e : g[u]) {
        int v = e.to;
        if (v == father || removed[v]) continue;
        getroot(v, u);
        mx[u] = max(mx[u], sz[v]);
    }
    mx[u] = max(mx[u], total - sz[u]);
    if (mx[u] < mx[root]) root = u;
}

// 把 u 的子树内所有点到分治中心的距离装进 dis。
void getdis(int u, int father, int d) {
    dis[++cnt] = d;
    for (const Edge &e : g[u]) {
        int v = e.to;
        if (v == father || removed[v]) continue;
        getdis(v, u, d + e.w);
    }
}

// 处理"经过 u"的路径。关键顺序：先拿本子树去查桶，再把本子树写进桶。
// 如果反过来，同一子树内的两个点也会被配上，而它们的路径根本不经过 u。
void calc(int u) {
    ++stamp;
    used[0] = stamp; // u 自己：距离 0 已占用，于是"u 到某点"的路径也能被找到

    for (const Edge &e : g[u]) {
        int v = e.to;
        if (removed[v]) continue;

        cnt = 0;
        getdis(v, u, e.w);

        // 1. 查询：本子树的每个距离，去桶里找补数
        for (int i = 1; i <= cnt; ++i) {
            for (int j = 0; j < m; ++j) {
                if (ok[j]) continue;
                long long need = (long long)qs[j] - dis[i];
                if (need >= 0 && need <= maxk && used[need] == stamp) {
                    ok[j] = 1;
                }
            }
        }

        // 2. 标记：本子树正式加入桶，供后面的兄弟子树配对
        for (int i = 1; i <= cnt; ++i) {
            if (dis[i] <= maxk) used[dis[i]] = stamp;
        }
    }
}

void solve(int u) {
    removed[u] = true;
    calc(u);

    for (const Edge &e : g[u]) {
        int v = e.to;
        if (removed[v]) continue;
        total = getsz(v, u);
        root = 0;
        mx[0] = total + 1;
        getroot(v, u);
        solve(root);
    }
}

void divide() {
    total = getsz(1, 0);
    root = 0;
    mx[0] = total + 1;
    getroot(1, 0);
    solve(root);
}
/*------------------------ 点分治（多询问） 代码 结束 ------------------------*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    init(n);
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }

    qs.resize(m);
    maxk = 0;
    for (int i = 0; i < m; ++i) {
        cin >> qs[i];
        maxk = max(maxk, qs[i]);
    }

    used.assign(maxk + 1, 0); // 桶的下标是"距离"，只需覆盖到最大询问
    ok.assign(m, 0);
    stamp = 0;

    divide();

    for (int i = 0; i < m; ++i) {
        cout << (ok[i] ? "AYE" : "NAY") << '\n';
    }
    return 0;
}

配合时间戳 stamp，每换一个分治中心只需 ++stamp，不用把整个桶清空——否则每组数据的清空代价就是 $O(\max K)$ 。

两种写法的取舍：

	容斥 + 排序	边收集边标记
适用	统计数量（可加的量）	判断存在、或统计需要取 $\min/\max$ 的量
额外开销	每个阈值一次排序， $O(\log)$	每个询问每个距离一次查询
空间	$O(n)$	$O(\max K)$
坑	减法必须精确、起点要带边权	①查询必须在②标记之前

8 复杂度

设当前层各连通块大小之和为 $O(n)$ 。每个连通块要做：求块大小、求重心、收集距离各 $O(m)$ ；排序 $O(m\log m)$ 。所以单层总开销是 $O(n\log n)$ 。

层数是 $O(\log n)$ ，因此总时间

O(n\log^2 n).

空间是 $O(n)$ ：sz、mx、dis、邻接表都是线性的；递归栈深度 $O(\log n)$ 。

如果能用一个值域桶代替排序（询问值很小或距离范围很窄时），单层可以降到 $O(n)$ ，总时间变成 $O(n\log n)$ 。[ luogu P2634] 就是这种情形：它只关心距离模 $3$ 的余数，桶只要 $3$ 个格。

9 经典例题

一、模板题：多次询问是否存在距离 $K$

[ luogu P3806]

就是上面「边收集边标记」那份模板，直接可过。它的定位是让你确认三件事做对了：重心选择、total 重算、查询与标记的顺序。

二、统计不超过 $K$ 的点对数量

[ luogu P4178]

即本文主模板 point_divide.cpp。若 $K$ 较小，可以把排序换成值域桶 + 树状数组，把 $O(\log^2 n)$ 优化到 $O(n\log n)$ 。

三、余数类：距离为 3 的倍数

[ luogu P2634]

只关心距离模 $3$ 的余数，所以收集距离时不必存真实值，直接 %3。桶只需 cnt[0..2] 三个格，配对规则是：

余数 $0$ 配 $0$ ： $cnt[0]\times cnt[0]$
余数 $1$ 配 $2$ ： $2\times cnt[1]\times cnt[2]$

最后除以总点对数 $n^2$ 并约分。这题是把「统计量的值域很小」换成「不需要排序」的典型。

四、最小化类：恰好 $K$ 且边数最少

[ luogu P4149]

给一棵 $n\le 2\times 10^5$ 的树，求一条边权和恰好为 $K$ 的简单路径中，边数最少的是几条。

统计量从「个数」变成了「最小值」，所以可以做容斥，但桶里存的不是布尔值而是最小边数：best[d] 表示到当前中心距离为 $d$ 的点里，最少用了多少条边。处理顺序仍然是「先查后标」，查的时候用 best[K-d]+当前边数 更新答案。

这题还有个容易忽略的细节：点从 $0$ 开始编号，读入后统一 +1 更省事。另外 $n$ 达到 $2\times 10^5$ ，链形数据下递归 DFS 的深度可能到 $2\times 10^5$ ，栈要留够或改手工栈。

10 点分治与相邻技术

技术	适合的问题	与点分治的关系
树上 DP / 换根 DP	能以子树或全局为单位递推的量	优先考虑，通常 $O(n)$ 就够，别上分治
树链剖分（HLD）	路径修改、路径查询	处理「一条路径」，点分治处理「所有点对」
点分治	统计满足距离条件的点对	本层批量算跨中心的，其余递归
边分治	类似点分治，但按边切	需要先转二叉树，否则度数大会退化
动态点分治（点分树）	带修改的点对统计	把点分治的递归结构存下来当数据结构用

选择顺序上有一条经验：先在 $O(n)$ 的树形 DP 里找答案，找不到再考虑点分治。 很多看似「所有点对」的题，其实能在合并子树时递推出来。

11 易错点

total 没按当前连通块重算。 最常见的一类 WA。用最初的 $n$ 会让「父亲方向」偏大，重心选错，复杂度退化甚至答案错。
复用了上一层的 sz。 sz 是相对某个根算的，进入新连通块必须重新 getsz。
calc 里漏了 $u$ 自己。 距离 $0$ 不放进集合，所有以 $u$ 为一端的路径都会丢。
减子树时距离起点写成了 $0$ 。 子树 $v$ 里的点到 $u$ 至少要走 $w(u,v)$ ，起点必须是这条边的权值。
忘记排序就直接双指针。 双指针的前提是序列有序；漏掉 sort 会得到一个「看起来跑得通」的错误答案。
对布尔值做容斥。 容斥只对可加的量成立。问存在性时要先数出对数再判断是否大于 $0$ 。
边收集边标记时把顺序写反。 先标记再查询，会把同一子树内的点对误算成路径经过中心。
用 memset 清空整个桶。 每组数据清 $O(\max K)$ 会超时，用时间戳或只清用过的位置。
多组数据没清 removed 和邻接表。 上一组的分治标记残留会让这一组少遍历点。
递归深度按 $O(\log n)$ 估算。 分治层数确实是 $O(\log n)$ ，但 getroot、getsz、getdis 都是普通 DFS，在链形树上单个函数的递归深度可达 $O(n)$ 。 $n=2\times10^5$ 时要留意栈。
距离上界按最坏情况估。 $n=4\times10^4$ 、边权 $10^3$ 时距离和约 $4\times10^7$ ，还在 int 范围内；但边权或点数的量级一换就可能越界。距离和与点对计数这两类答案都建议直接开 long long。
桶内存按询问最大值开。 $k\le10^7$ 的桶约 $40\text{MB}$ ，能过但别再多开几份；多组数据共用同一个桶即可。

点分治

1 问题引入：一条路径一条路径算是来不及的

2 核心直觉：按「路径经过谁」分类

3 为什么中心必须选重心

4 统计经过 uuu 的路径：容斥

5 完整算法步骤

5.1 为什么 total 必须在每一层重算

6 模板代码

6.1 从「不超过 KKK」改成「恰好 KKK」