第 5.15 章：树上差分与点分治

5.15.0 从一道题出发：货运路径上的"距离恰好为 k"

先看一道 USACO 风格的题：

🚚 题目：货运路径 Farmer John 的农场有 N 个牧场（N ≤ 4×10⁴），由 N-1 条道路连接成一棵树，每条道路长度为 1。 接下来有 Q 次询问（Q ≤ 100），每次给出一个整数 k（k ≤ 2×10⁴），询问：树上距离恰好为 k 的无序点对 (u, v) 有多少个（u < v，两点可以相同则 u = v 时不计）。

先试试你会的方法

思路 1：每次询问 BFS 全树。 对每个 k，从每个点出发 BFS 一遍，数出距离为 k 的点。一次询问 O(N²)（或 O(N·k)），Q 次就是天文数字——超时。

思路 2：枚举所有点对求 LCA 算距离？ C(N, 2) ≈ 8×10⁸ 对，每对还要 O(log N) 求 LCA——也超时。

思路 3：DP？ "距离恰好为 k"涉及两段路径拼起来（u → lca → v），状态里"经过哪个分叉点"没法省掉，普通树形 DP（第 6.8 章）做不了任意 k 的全局计数。

关键观察： 问题的形态决定了武器——

• 如果修改/询问是**"先一堆路径修改、最后统一查询"（离线一次性），那就像数组差分一样，可以在树上做差分**：O(1) 给一条路径整体 +1，最后 O(N) 还原。
• 如果是**"全局统计所有点对"（本题！），那要用点分治**：每次挑树的重心，把所有路径按"是否经过重心"分成两类，层层分治下去。

本章讲这两个技术。它们共用同一块基石——第 5.13 章的倍增 LCA，以及第 5.12 章 5.12.1 节的树的重心。

拆解这一章需要回答的问题

1. 怎么把"路径整体 +1"变成 4 个单点修改？→ 5.15.1：树上差分
2. 全局路径统计为什么从重心开始？→ 5.15.2：点分治思想
3. 「距离为 k 的点对数」完整代码 → 5.15.3：排序 + 双指针 + 容斥
4. 还能问什么变形？→ 5.15.4：点分治变形一览

学习目标：

• 掌握点差分与边差分的修改公式与"子树求和还原"
• 理解点分治"选重心保证分治规模减半"的复杂度证明
• 独立实现「距离为 k 的点对数」，并会用容斥去重
• 分清树上差分（离线修改）与 HLD（在线查询）的适用边界

5.15.1 树上差分：路径修改的 O(1) 写法

回顾：数组差分

数组上想给区间 [l, r] 整体 +1，可以 diff[l]++, diff[r+1]--，最后扫一遍前缀和就还原出每个位置的真实值。核心是：修改打到端点上，求和时自然"摊开"。

树上差分做同样的事，只是"区间"换成了路径，"前缀和"换成了子树和。

点差分：路径上每个点 +1

先看公式。设 p = lca(u, v)，fa[p] 是 p 的父节点。要让路径 u → p → v 上的每个节点权值 +1：

diff[u]++    diff[v]++    diff[p]--    diff[fa[p]]--

为什么是对的？还原时对每个节点算以它为根的子树内 diff 之和：

        1                路径 4 → 5（lca = 2）：
       / \               diff[4]++  diff[5]++  diff[2]--  diff[1]--
      2   3
     / \                 还原（子树和）：1:0  2:1  3:0  4:1  5:1
    4   5                恰好路径 {4,2,5} 上的点 = 1 ✓

直观理解：点 x 的子树和 = "子树里所有 diff 修改，对 x 的净影响"。diff[u]++ 从 u 出发向上影响 u 到根的每个点；diff[p]-- 在 p 处把这份影响截断——但它自己也被抵消了，所以再给 fa[p]--……不对，是 fa[p]-- 会多减一次 p 之上的部分，正好把 diff[u]、diff[v] 中越过 p 的部分全部抵消。画图验证：u 子树和里包含 u 的 +1（u 在自己子树里 ✓），p 的子树和包含 4、5 的 +1 和 2 的 -1，净 +1 ✓，而 1 的子树和包含 +1+1-1-1 = 0 ✓。

边差分：路径上每条边 +1

树的边不好单独编号打标记，所以我们把每条边挂在它深度较大的端点上（"这条边通向我的父亲"）。要让路径 u → v 上的每条边 +1：

diff[u]++    diff[v]++    diff[p] -= 2

验证（同上图，路径 4 → 5，lca = 2）：

diff[4]++  diff[5]++  diff[2]-=2
还原（子树和，即"我挂的那条边的真实经过次数"）：
  边(1-2): 挂在 2 上，2 的子树和 = 1+1-2 = 0 ✓（路径不经过它）
  边(2-4): 挂在 4 上，4 的子树和 = 1 ✓
  边(2-5): 挂在 5 上，5 的子树和 = 1 ✓

与点差分的区别：p 自己也被 lca 处的 -1 抵消了"向父亲那条边"的份额，所以直接 -= 2 一次搞定，不需要动 fa[p]。

完整代码：路径加 + 最后查询每个点/每条边的经过次数

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

const int MAXN = 100005, LOG = 17;
int n;
vector<pair<int,int>> adj[MAXN];   // (邻居, 边编号)
int dep[MAXN], fa[LOG][MAXN];
int diffPoint[MAXN];               // 点差分
int diffEdge[MAXN];                // 边差分：挂在"深度较大端点"上

void dfs(int u, int f) {
    dep[u] = dep[f] + 1;
    fa[0][u] = f;
    for (int j = 1; j < LOG; j++) fa[j][u] = fa[j-1][fa[j-1][u]];
    for (auto [v, id] : adj[u]) {
        if (v == f) continue;
        dfs(v, u);
    }
}
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int j = LOG-1; j >= 0; j--)
        if (dep[fa[j][u]] >= dep[v]) u = fa[j][u];
    if (u == v) return u;
    for (int j = LOG-1; j >= 0; j--)
        if (fa[j][u] != fa[j][v]) { u = fa[j][u]; v = fa[j][v]; }
    return fa[0][u];
}

// 路径 u-v 上每个点经过次数 +1（点差分）
void addPathPoint(int u, int v) {
    int p = lca(u, v);
    diffPoint[u]++; diffPoint[v]++;
    diffPoint[p]--; diffPoint[fa[0][p]]--;
}
// 路径 u-v 上每条边经过次数 +1（边差分）
void addPathEdge(int u, int v) {
    int p = lca(u, v);
    diffEdge[u]++; diffEdge[v]++; diffEdge[p] -= 2;
}

int cntPoint[MAXN], cntEdge[MAXN]; // 子树求和还原后的结果
void collect(int u, int f) {
    cntPoint[u] = diffPoint[u];
    cntEdge[u] = diffEdge[u];
    for (auto [v, id] : adj[u]) {
        if (v == f) continue;
        collect(v, u);
        cntPoint[u] += cntPoint[v];
        cntEdge[u] += cntEdge[v];
    }
}

int main() {
    // 测试树：
    //        1
    //       / \
    //      2   3
    //     / \    \
    //    4   5    6
    n = 6;
    int us[] = {1,1,2,2,3}, vs[] = {2,3,4,5,6};
    for (int i = 0; i < 5; i++) {
        adj[us[i]].push_back({vs[i], i});
        adj[vs[i]].push_back({us[i], i});
    }
    dfs(1, 0);
    // 3 条路径：2->6（2-1-3-6）、4->5（4-2-5）、1->6（1-3-6）
    addPathPoint(2, 6); addPathPoint(4, 5); addPathPoint(1, 6);
    addPathEdge(2, 6); addPathEdge(4, 5); addPathEdge(1, 6);
    collect(1, 0);
    // 手算期望：
    // 点：1:2  2:2  3:2  4:1  5:1  6:2
    // 边：(1-2):1 (1-3):2 (2-4):1 (2-5):1 (3-6):2
    printf("点经过次数：");
    for (int u = 1; u <= n; u++) printf("%d=%d ", u, cntPoint[u]);
    printf("\n边经过次数：");
    for (int i = 0; i < n-1; i++) {
        int a = us[i], b = vs[i];
        int child = dep[a] > dep[b] ? a : b;   // 边挂在深度较大的端点
        printf("(%d-%d)=%d ", us[i], vs[i], cntEdge[child]);
    }
    printf("\n");
    return 0;
}

运行输出：

点经过次数：1=2 2=2 3=2 4=1 5=1 6=2
边经过次数：(1-2)=1 (1-3)=2 (2-4)=1 (2-5)=1 (3-6)=2

与手算完全一致。collect 就是一次 DFS 求子树和，复杂度 O(N)。

与树链剖分（第 5.12 章）对比

选择口诀： 题目如果是"先给一堆路径操作、最后问每个点/边的累计值"（USACO 常见的"流量统计"型），树上差分是最快的答案；一旦需要边修改边查询，差分立刻失效，只能上 HLD。

5.15.2 点分治：从重心开始的全局统计

回到开篇题：统计全树所有距离为 k 的点对。树上差分帮不上忙——它处理"路径修改"，这里要的是"路径计数"。

核心观察：经过根的路径 + 不经过的路径

随便选个节点 rt 当根。任何一条路径必然属于且仅属于下面两类之一：

1. 经过 rt——可以拆成"u 到 rt"和"rt 到 v"两条链，在 rt 处统计；
2. 不经过 rt——它完整落在 rt 的某一棵子树里，递归处理。

这两类不重不漏：一条路径要么经过 rt 要么不经过。递归的每一层把"经过当前根"的部分统计掉，剩下的交给子树——这就是点分治。

为什么必须选重心？

递归深度取决于子树规模。随便选根（比如树的端点），树是一条链时每次只切掉 1 个点，递归 N 层，每层 DFS 整棵树，总复杂度 O(N²)——退化成暴力。

选重心（5.12.1 节）就不同了：重心保证每棵子树 ≤ 总规模的一半。于是每层分治，连通块规模至少减半：

N → N/2 → N/4 → ... → 1        共 O(log N) 层

每一层内，所有连通块的 DFS 加起来恰好处理每个点一次（O(N)），所以总复杂度 O(N log N)。这就是"点分治"名字里"分"的含金量。

容斥去重：减去同一棵子树里的"假路径"

统计"经过 rt 的路径"时有个陷阱。设 rt 有两个孩子 a、b，子树 a 里有点 u、子树 a 里另有点 v。如果我们简单地"收集整个 rt 连通块内所有点到 rt 的距离，两两配对"，dist(u) + dist(v) = k 时会把 u → rt → v 当成一条合法路径——但 u 到 v 的真实路径根本不经过 rt（它们在 a 的子树里，LCA 是 a 不是 rt）！这条路径会在递归 a 的子树时再被统计一次，重复了。

解决办法是容斥：

答案（经过 rt 的部分） = 所有链两两配对 − 同一棵子树内的链两两配对

同一棵子树内的配对被减掉后，剩下的恰好是"两条链来自不同子树"（真路径，LCA 恰为 rt）加上"一条链长为 0"（路径端点就是 rt）。注意：端点是 rt 的路径（链配对里 0 + k 的情形）不会被容斥误减——因为被减掉的配对里如果一边是 0（rt 自己），它到 rt 的距离 0 只会在"全部链"的数组里出现一次，不在任何子树的数组里。

💡 容斥口诀： 先把 rt 所有子树的距离混在一起数一遍，再逐个子树单独数一遍减掉。剩下的就是不重不漏的"经过 rt"。

5.15.3 完整实战：距离为 k 的点对数

框架

solve(u)：                       // u 是当前连通块的重心
    vis[u] = true                // "删掉" u，之后所有 DFS 跳过它
    all = {0} ∪ 各子树内所有点到 u 的距离
    ans += count(all)            // 经过 u 的所有点对（含 u 为端点）
    for 每个孩子子树 s：
        ans -= count(s 的距离)    // 容斥：同子树内的假路径
    for 每个还没删的连通块：
        solve(该连通块的重心)

统计"距离和为 k 的对数"：排序 + 双指针

把距离数组排序后，用相向双指针：a[i] + a[j] < k 时 i++，> k 时 j--，== k 时处理一段相等的值（左右各有多少个，乘起来），注意 a[i] == a[j] 时剩余全部相等，用组合数 C(cnt, 2)。

完整代码

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

const int MAXN = 100005;
int n;
vector<pair<int,int>> adj[MAXN];   // (邻居, 边权)
bool vis[MAXN];                    // true = 已经当过分治中心（"已删除"）
int sz[MAXN], mxson[MAXN];
int K;
long long ans = 0;

// ---- 第 1 步：在"当前连通块"里找重心 ----
// sum = 当前连通块的总点数（注意不是整棵树的 n！）
int sum, root, rootMax;
void getRoot(int u, int fa) {
    sz[u] = 1; mxson[u] = 0;
    for (auto [v, w] : adj[u]) {
        if (v == fa || vis[v]) continue;
        getRoot(v, u);
        sz[u] += sz[v];
        mxson[u] = max(mxson[u], sz[v]);
    }
    mxson[u] = max(mxson[u], sum - sz[u]);
    if (mxson[u] < rootMax) { rootMax = mxson[u]; root = u; }
}
int findRoot(int start, int total) {
    sum = total; rootMax = INT_MAX; root = -1;
    getRoot(start, 0);
    return root;
}
// 统计一个还没删的连通块的大小
int calcSize(int u, int fa) {
    int res = 1;
    for (auto [v, w] : adj[u]) {
        if (v == fa || vis[v]) continue;
        res += calcSize(v, u);
    }
    return res;
}

// ---- 第 2 步：收集子树内所有点到分治中心的距离 ----
int dis[MAXN];
vector<int> cur;                    // 当前子树收集到的距离
void getDis(int u, int fa, int d) {
    dis[u] = d;
    cur.push_back(d);
    for (auto [v, w] : adj[u]) {
        if (v == fa || vis[v]) continue;
        getDis(v, u, d + w);
    }
}

// 排序 + 双指针：有序距离数组中和恰好为 K 的点对数
// 数组含 0（即"一个端点是分治中心"的链）
long long countPairs(const vector<int>& d) {
    vector<int> a = d;
    sort(a.begin(), a.end());
    long long res = 0;
    int i = 0, j = (int)a.size() - 1;
    while (i < j) {
        if (a[i] + a[j] == K) {
            if (a[i] == a[j]) {              // 剩下全部相等，C(cnt, 2)
                long long c = j - i + 1;
                res += c * (c - 1) / 2;
                break;
            }
            int hi = i;  while (hi + 1 <= j && a[hi + 1] == a[i]) hi++;
            int lj = j;  while (lj - 1 >= i && a[lj - 1] == a[j]) lj--;
            res += (long long)(hi - i + 1) * (j - lj + 1);
            i = hi + 1; j = lj - 1;
        } else if (a[i] + a[j] < K) i++;
        else j--;
    }
    return res;
}

// ---- 第 3 步：solve(u)：统计"经过 u"的答案，然后递归子连通块 ----
void solve(int u) {
    vis[u] = true;

    // (a) 所有子树的距离混在一起 + 中心自己的 0
    vector<int> all;
    all.push_back(0);                 // u 自己（处理"端点是 u"的路径）
    for (auto [v, w] : adj[u]) {
        if (vis[v]) continue;
        cur.clear();
        getDis(v, u, w);              // 子树 v 内所有点到 u 的距离
        for (int d : cur) all.push_back(d);
    }
    ans += countPairs(all);           // 经过 u 的所有点对

    // (b) 容斥：减去"两端在同一棵子树"的假路径
    for (auto [v, w] : adj[u]) {
        if (vis[v]) continue;
        cur.clear();
        getDis(v, u, w);
        ans -= countPairs(cur);       // 它们会在更深层被重新统计
    }

    // (c) 递归处理每个还没被删的连通块
    for (auto [v, w] : adj[u]) {
        if (vis[v]) continue;
        solve(findRoot(v, calcSize(v, u)));   // 大小是当前连通块，不是 n！
    }
}

int main() {
    // 测试树（边权全 1）：
    //        1
    //       /|\
    //      2 3 4
    //     /|     \
    //    5 6      7
    // K = 3 时，距离恰为 3 的点对（暴力 Floyd 交叉验证）：
    // {2,7} {3,5} {3,6} {3,7} {4,5} {4,6}  共 6 对
    n = 7; K = 3;
    int us[] = {1,1,1,2,2,4}, vs[] = {2,3,4,5,6,7};
    for (int i = 0; i < 6; i++) {
        adj[us[i]].push_back({vs[i], 1});
        adj[vs[i]].push_back({us[i], 1});
    }
    solve(findRoot(1, n));
    printf("距离为 %d 的点对数 = %lld（期望 6）\n", K, ans);
    return 0;
}

运行输出：

距离为 3 的点对数 = 6（期望 6）

代码要点逐条对账

• vis[u] 充当"删除"：点分治里的"分治中心"处理完就永久删除，所有 DFS（getRoot/getDis/calcSize）遇到 vis 的点一律跳过——这等价于"删掉 u 后树分裂成若干连通块"。
• calcSize(v, u) 而不是 n：递归时连通块已经变小，找重心时"向上那部分"必须用当前连通块大小计算（见下方常见错误 3）。
• 容斥只减不加：(b) 对每个子树单独数一遍并减掉。想验证正确性，可以在小树上跑一遍 Floyd 暴力对拍。

5.15.4 点分治变形一览

点分治是框架，框架不变，"统计经过根的路径"这一步按题意换：

💡 识别信号： 看到"树上所有点对的路径满足……的计数/存在性"且 N ≤ 10⁵，几乎必然是点分治（或点分树）。

⚠️ 常见错误

1. 点差分忘了 diff[fa[lca]]--、边差分减错位置： 点差分是 4 处修改 diff[u]++ diff[v]++ diff[p]-- diff[fa[p]]--——少写最后一项，LCA 之上的所有点会被多算；边差分是 diff[p] -= 2——写成两个 -1 没问题，但只减 1 次（照抄点差分）就错了。两个公式不要互相"半抄"。

2. 点分治忘了 vis 标记 / 删旧中心： vis[u] = true 必须在统计之前打上，且 getRoot、getDis、calcSize 里都要 if (vis[v]) continue;。漏掉任何一处，DFS 会穿过"已删除"的中心把别的连通块也扫进来——答案错、还可能死递归。

3. 递归找重心时用整棵树的 N 而不是当前连通块大小： getRoot 里 mxson[u] = max(mxson[u], sum - sz[u]) 的 sum 必须是当前连通块的点数。用全局 n 会导致找到的"重心"不对，最坏退化成 O(N²)——代码"看起来能过小样例"但大样例 TLE，极难排查。

4. 容斥漏减（或重复减）： (a) 步把所有子树距离混在一起统计后，(b) 步必须对每个子树单独再统计并减掉。只做 (a) 不做 (b) 会把"LCA 不是当前中心"的路径多算；反过来，如果容斥数组里误含了中心自己的 0，会把"端点是中心"的合法路径误减——(b) 的数组来自 getDis(v, u, w)，天然不含中心，别手滑加进去。

📋 章节小结

📌 核心要点

❓ 常见问题

Q：树上差分和第 5.12 章的 HLD 什么时候用哪个？
A：题目是"一堆路径修改 + 最后统一查询" → 树上差分（代码 40 行，最快）；需要"边修改边查询"（在线）→ HLD + 数据结构。

Q：点分治每次找重心，会不会找得很慢？
A：每层所有连通块的 DFS 总量是 O(当前总规模)，而规模每层减半，所以所有层加起来 O(N log N)——找重心不额外增加复杂度。

Q：点分治能处理带负边权的树吗？
A：能。"距离"只是 DFS 收集的数，排序双指针对负数照样工作；只有最短路类算法（Dijkstra）才怕负权。

🔗 与其他章节的联系

• [第 5.12 章 5.12.1（树的重心）： 点分治的复杂度支柱，本章直接引用其求重心代码。
• [第 5.13 章（倍增 LCA）： 树上差分每次修改求 LCA 用它。
• [第 5.8 章（BIT）： 若"距离为 k"改成"边权在 [a,b] 的路径数"，点分治统计阶段可换 BIT 维护。

🏋️ 练习题

🟢 简单

5.15-E1. 道路流量 （USACO 风格）
N 个节点的树（N ≤ 10⁵）。给出 M 条运输路径 (u, v)（M ≤ 10⁵），最后询问：哪条边被经过的次数最多？输出该边及次数。
数据规模： 1 ≤ N, M ≤ 10⁵。

🟡 中等

5.15-M1. 距离不超过 K 的点对 （P4178 Tree）
N 个节点的带权树，问距离 ≤ K 的无序点对有多少个。
数据规模： N ≤ 4×10⁴，K ≤ 2×10⁴，边权 ≤ 10³。

🔴 困难

5.15-H1. 树上路径公共边计数 （USACO 风格）
N 个节点的树。给定 M 条路径 (u_i, v_i)，对每条边 e，求有多少对路径同时经过 e。
数据规模： 1 ≤ N, M ≤ 10⁵。