树上差分与子树和

树上差分与子树和：像发糖果一样快速统计路径覆盖

在学习和生活中，我们经常遇到这样的问题：比如班级里有个社团组织，社长（根节点）下面有小组长，小组长下面有成员，形成一棵树。现在要组织一次活动，需要给从某个成员A到另一个成员B路径上的所有人都发一颗糖果，活动重复多次，最后想知道每个人一共得到了多少颗糖果。如果每次活动都亲自沿着路径走一遍，挨个发，那么人数多了、次数多了就会非常慢。有没有更聪明的方法呢？

树上差分就是用来解决这类“树上路径批量加减，最后求每个节点值”的得力工具。它借鉴了普通数组差分的思路——先把加减操作记录在几个关键位置，最后通过一次遍历累加，就能算出最终结果。这样做的好处是：每次操作只需要修改常数个节点，最后通过一次DFS（深度优先搜索）就能得到所有节点的答案，效率极高。

核心思想：在起点和终点加，在最近公共祖先（LCA）处减

假如我们要给树上的路径 (u, v) 上所有节点都加上同一个值 x（比如1颗糖果）。按照树上差分的经典做法，我们只需要修改四个位置（有些情况可能少于四个）：

在节点 u 的差分数组 diff[u] 上加 x
在节点 v 的差分数组 diff[v] 上加 x
在 u 和 v 的最近公共祖先 lca 的差分数组 diff[lca] 上减 x
在 lca 的父节点 parent[lca] 的差分数组 diff[parent[lca]] 上减 x（如果 lca 不是根节点）

为什么要这样加加减减？我们可以用一个生活中的例子来理解。

生活例子：发糖果的接力
想象一棵树代表社团的直属关系。根节点是社长，每个节点是一个成员。现在要从成员A（节点2）到成员B（节点5）的路径上所有成员发1颗糖果。这个路径是：2 → 1 → 0 → 4 → 5（假设根是0）。我们并不真的沿着路径一个个发，而是像做记号一样：

在A（节点2）和B（节点5）处各放一个 “起始标记”，表示从这里开始要发一颗。
但是从A到根的路径和从B到根的路径会重合，在公共祖先（节点0）处会重复计数。所以我们在公共祖先处放一个 “终止标记” 减去一颗，避免多算。
但公共祖先自己也是路径上的节点，应该得到一颗。如果只减公共祖先，它的值就会少算。于是我们还需要在公共祖先的父节点（本题中根没有父节点，如果有的话）再减一颗，这样经过最终累加，公共祖先的值就会正确。

最终我们通过一次从根开始的DFS，把每个节点的差分值 向上累加（或者说是把子树的差分和传递给父节点），就能得到每个节点的实际糖果数。

具体操作步骤

建树：用邻接表存储树。
预处理LCA：因为我们需要知道任意两个节点的最近公共祖先，所以需要先进行LCA的预处理（通常用倍增法或Tarjan算法）。为了简化，在本文的例子中，我们假设已经知道LCA，直接给出结果。 实际应用中必须写好LCA代码。
执行每次路径加操作：按照上述规则修改 diff 数组。
一次DFS求子树和：从根节点开始递归，cur 表示从根到当前节点路径上所有 diff 值的累加和。对于每个节点 u，它的最终值就是当前的 cur （因为 cur 已经包含了从根到 u 这条路径上的所有差分贡献，而树上差分的性质保证这个累加和恰好等于所有以 u 为端点的路径操作叠加后的结果）。

注意：这里的“子树和”其实是指从根到当前节点的路径累加，因为每个节点的值等于所有它祖先节点的差分值之和（加上它自己的差分值）。更准确地说，我们在DFS中做的是前缀和，而不是子树和。但习惯上，树上差分常常通过DFS求子树和的方式来实现（即 diff[u] += sum(diff[child])），然后每个节点的值就是它自己的 diff 加上所有子节点的贡献。两种方法本质等价，本文采用更直观的“路径前缀和”DFS方法。

新手容易犯的错误

❌ 忘记修改LCA的父节点
如果 lca 不是根节点，必须在 parent[lca] 处也减去 x。否则 lca 以外的节点（包括 lca 的祖先）会多算一次。

❌ LCA的计算错误
求错LCA会导致整个差分错误。一定要确保写对了倍增或Tarjan，并且在树根不是0时注意边界。

❌ DFS累加时混淆了 diff 的原始值与累加值
在递归中，我们应当用一个独立的变量保存当前累加和（如 cur），而不是直接修改 diff[u]。如果直接修改 diff 作为累加结果，后续回溯会出问题。

❌ 忽略根节点的父节点
如果根节点也出现在路径中且作为LCA，根没有父节点，那么就不要做 parent[lca] 的减法。常见的写法是判断 lca != root 时才减父节点。

完整可运行示例（含注释）

下面我们给出一个完整的C++代码，展示如何使用树上差分对树上的路径进行批量加1操作，并输出每个节点最终的值。为了代码简洁，我们手动指定了树的形状和LCA，实际使用中你需要实现LCA求法（例如倍增法）。

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1005;

vector<int> adj[MAXN];   // 邻接表存树
int diff[MAXN];          // 差分数组，初始为0

// DFS 求每个节点的实际值
// u: 当前节点， parent: 父节点， cur: 从根到u的前缀累加和
void dfs_calc(int u, int parent, int cur) {
    cur += diff[u];                     // 加上当前节点的原始差分值
    int value = cur;                    // 这是节点u最终的覆盖次数
    cout << "节点 " << u << " 的最终值: " << value << endl;

    for (int v : adj[u]) {
        if (v == parent) continue;      // 避免回到父节点
        dfs_calc(v, u, cur);            // 递归处理子节点
    }
}

int main() {
    int n = 6;  // 节点数，假设节点编号0~5
    // 构建一棵树：
    //       0
    //      / \
    //     1   2
    //    /|   |
    //   3 4   5
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[1].push_back(3); adj[3].push_back(1);
    adj[1].push_back(4); adj[4].push_back(1);
    adj[2].push_back(5); adj[5].push_back(2);

    // 想象我们进行了多次路径加法操作。这里演示一次：
    // 给路径 (3, 5) 上所有节点加 1
    // 路径：3-1-0-2-5，LCA是0，parent[0]==-1（根无父节点）
    int u = 3, v = 5, lca = 0, parent_lca = -1;
    int x = 1;  // 加1

    diff[u] += x;
    diff[v] += x;
    diff[lca] -= x;
    // 因为lca是根，没有父节点，所以不做diff[parent[lca]]-=x

    // 如果还有其他路径操作，继续修改diff数组……
    // 例如再给路径 (1, 2) 加2，LCA=0
    u = 1; v = 2; lca = 0;
    x = 2;
    diff[u] += x;
    diff[v] += x;
    diff[lca] -= x;

    cout << "所有操作后，各节点的最终值：" << endl;
    dfs_calc(0, -1, 0);    // 从根节点开始累加
    return 0;
}

运行结果（手动计算）：

第一次操作路径(3,5)加1：经过3,1,0,2,5。
第二次操作路径(1,2)加2：经过1,0,2。
合并后：
节点3:1，节点1:1+2=3，节点0:1+2=3？注意LCA处的减法抵消，实际上0得到1+2-1? 我们来算一下：第一次操作，diff[3]+=1, diff[5]+=1, diff[0]-=1; 第二次操作，diff[1]+=2, diff[2]+=2, diff[0]-=2。最终diff数组：diff[0]=-3, diff[1]=2, diff[2]=2, diff[3]=1, diff[4]=0, diff[5]=1。DFS累加：
根0: cur=-3 → 节点0值=-3？不对！按理说0应该被覆盖3次才对。问题出在哪里？
哦，我们发现了一个经典错误：LCA的减法应该只在diff[lca]处减一次，而不应在根节点再多减。实际上正确的做法是：对于每个操作，在 diff[lca] -= x，同时如果 lca 不是根，还要在 diff[parent[lca]] -= x。这里的根没有父节点，所以第二次操作时 lca=0，我们只减了 diff[0]-=2。第一次也只减了 diff[0]-=1，所以 diff[0] 总共是 -3。但路径上0确实被覆盖了三次（第一次一次，第二次两次），应该有值3。这样累加从根开始，根的值就是 curr = diff[0] = -3，这显然是错的。

关键点：我们搞混了两种常用的树上差分写法。正确的做法（用于求点覆盖次数）是：

对于路径(u,v)，令 diff[u] += x，diff[v] += x，diff[lca] -= 2*x，而不是减去一次。为什么？因为从根到u的路径和从根到v的路径在lca处分叉，如果只在lca处减一次，那么lca到根的路径会被重复加两次。实际上每个操作应该这样：
diff[u] += x; diff[v] += x; diff[lca] -= 2*x;
然后DFS时，每个节点的值等于其子树 diff 之和。这种写法适用于“边覆盖”还是“点覆盖”？我们来推导一下。

重要纠正：树上差分有两种常见模型：

边差分：给路径上的每条边加x，则 diff[u] += x; diff[v] += x; diff[lca] -= 2*x; 最后每个节点 diff 的子树和就是该节点到父节点这条边的覆盖次数。
点差分：给路径上的每个点加x，则 diff[u] += x; diff[v] += x; diff[lca] -= x; diff[parent[lca]] -= x;（如果lca不是根）。最后每个节点的值等于其子树 diff 之和（注意这里的子树和是真正的子节点贡献累加，而不是前缀和）。或者也可以用另一种等价写法：diff[u] += x; diff[v] += x; diff[lca] -= 2*x; 然后最后再单独给每个节点加上根到它的前缀和？大家容易混淆。

为了清晰，本文采用点差分的第一种写法（加上父节点减）。但是之前手动计算错误是因为我们错误地使用了减法次数。让我们重新修正上面的代码和计算：

正确的点差分操作：
对于路径(u,v)，设 lca 是最近公共祖先。

diff[u] += x
diff[v] += x
diff[lca] -= x
如果 lca 有父节点 p，则 diff[p] -= x

然后最终每个节点的值 = 它的 diff 值 + 所有子节点 diff 之和（即从下往上累加子树和）。注意这里的方向：是从叶子向根累加，而不是从根向叶子累加。之前的代码 dfs_calc 是从根向下累加，这是前缀和的方式，适用于另一种变体。对于点差分的标准做法，应该先用DFS求出每个节点的子树和，然后节点值就是该子树和。

下面给出正确的完整示例，使用子树和方式（更适合点差分）：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1005;
vector<int> adj[MAXN];
int diff[MAXN];      // 差分数组
int ans[MAXN];       // 最终每个节点的值

// DFS求子树和（从叶子往上累加）
void dfs_sum(int u, int parent) {
    int sum = diff[u];        // 先加上当前节点自己的差分
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs_sum(v, u);
        sum += ans[v];        // 加上子节点的最终值（子节点的子树和已经包含它自己的贡献）
    }
    ans[u] = sum;             // 当前节点的最终值 = 自己的差分 + 所有子节点的ans
}

int main() {
    int n = 6;
    // 构建树同上
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[1].push_back(3); adj[3].push_back(1);
    adj[1].push_back(4); adj[4].push_back(1);
    adj[2].push_back(5); adj[5].push_back(2);

    // 第一次操作：路径(3,5)加1，LCA=0，parent[0]=-1（不存在）
    int u = 3, v = 5, lca = 0, parent_lca = -1;
    int x = 1;
    diff[u] += x;
    diff[v] += x;
    diff[lca] -= x;           // 因为lca是根，无父节点，不需要再减
    // 注意：这里只减了一次，因为lca是根，路径上的点包括3,1,0,2,5
    // 但按照点差分公式，还需要在parent[lca]处减x，但parent不存在，所以跳过。

    // 第二次操作：路径(1,2)加2，LCA=0，同样无父节点
    u = 1; v = 2; lca = 0;
    x = 2;
    diff[u] += x;
    diff[v] += x;
    diff[lca] -= x;

    // 此时diff数组为：
    // diff[3]=1, diff[5]=1, diff[1]=2, diff[2]=2, diff[0]= -1 -2 = -3

    // 从根开始DFS求子树和
    dfs_sum(0, -1);

    // 输出结果
    cout << "每个节点最终被覆盖的次数：" << endl;
    for (int i = 0; i < n; ++i) {
        cout << "节点 " << i << " : " << ans[i] << endl;
    }
    return 0;
}

手动验证：

节点3: 只有diff[3]=1，叶子节点，子节点无，ans[3]=1。
节点5: ans[5]=1。
节点1: diff[1]=2，子节点3和4，ans[3]=1, ans[4]=0，所以ans[1]=2+1+0=3。
节点2: diff[2]=2，子节点5，ans[5]=1，所以ans[2]=2+1=3。
节点0: diff[0]=-3，子节点1和2，ans[1]=3, ans[2]=3，所以ans[0]= -3+3+3=3。
节点4: ans[4]=0。

结果：节点0、1、2都被覆盖了3次，节点3和5被覆盖1次，节点4为0。与预期一致（第一次操作覆盖了0,1,2,3,5，第二次覆盖了0,1,2，所以0被覆盖2次？不，第一次覆盖了0，第二次也覆盖了0，所以0应该是3次？是的，两次操作都经过0，所以0被覆盖3次。正确。）

所以上面的代码是正确的。注意：这里我们采用了子树和（从底向上累加），而不是之前的前缀和。两种方式都可以，但必须匹配相应的差分公式。