树上差分

本篇对应源码见仓库 solutions/xcpc/algorithm/prefix/difference/。

以下以「带权路径更新」为例，分别介绍树上差分的两种常见变体——节点差分（点差分）和边差分（边上差分）。要点在于如何打标记（diff[] 数组）和如何在一次 DFS 中恢复。

0. 共同前提：LCA 预处理

在做任意两点 u,vu,v 之间的路径更新前，需先用二进制提升或倍增法预处理出每个节点的 $up[k][x]$ 和深度 $depth[x]$ ，并实现

int lca(int u, int v);

这里不赘述，假设已有 $O(N \log N)$ 的 LCA。

1. 边差分（Edge Difference）

目标：对每次查询 “给路径 $u→v$ 上的每条边加上权值  $+ w$ ”；最后求出所有边的累加结果。

1.1 标记策略

对于一次 “ $u\to v$ 路径上每条边 $+w$ ” 操作，记 $w$ 为更新值，令

diff[u]       += w;
diff[v]       += w;
diff[lca(u,v)] -= 2*w;

这样做的含义是：

从 u 向上走到根，会累加一次 +w；
从 v 向上走到根，会累加一次 +w；
但在最低公共祖先 p=lca(u,v) 处，+2w 应该抵消（因为从两边都走到它），所以做 $-2w$ 。

1.2 恢复与答案采集

选定 1 号节点为根，执行一次后序 DFS：

void dfs(int u,int p){
    for(auto [v,eid]: adj[u]){
        if(v==p) continue;
        dfs(v,u);
        // v 子树累积到 u
        diff[u] += diff[v];
        // 边 (u,v) 上被加的总权值，正是 diff[v]
        ans_edge[eid] = diff[v];
    }
}

diff[x] 最终表示 “从子树 x 往上经过的所有更新贡献之和”；
每条边答案即是它下面子树根点的 diff[v]。

1.3 复杂度

LCA 预处理： $O(N \log N)$
每次更新打标： $O(1)$
最后 DFS 聚合： $O(N)$ 总计： $O(N \log N + Q + N)$

2. 点差分（Node Difference）

目标：对每次查询 “给路径 $u→v$ 上的每个节点加上权值  $+ w$ ”；最后求出所有节点的累加结果。

2.1 标记策略

这次我们要保证从 u 到 v 两端都各加 +w，但节点 p=lca(u,v) 被算了两次，需要抵消一次；且它的父节点 $fa[p]$ 也要抵消一次，否则从它往上的累加会多出一份。具体做：

diff[u]         += w;
diff[v]         += w;
diff[p]         -= w;
if (fa[p] != 0) diff[fa[p]] -= w;

其中 fa[p]=up[0][p] 是 $p$ 的父节点。

+w 打在 u,v 保证两边都能传播；
在 LCA 处 -w 抵消双算；
在 LCA 的父节点再 -w，防止它以上的祖先节点被多加一次。

2.2 恢复与答案采集

同样一次后序 DFS：

void dfs(int u,int p){
    for(int v: adj[u]){
        if(v==p) continue;
        dfs(v,u);
        // 子节点 v 的 diff 先累到 u
        diff[u] += diff[v];
    }
    // 至此 diff[u] 就是最终点 u 上的答案
    ans_node[u] = diff[u];
}

2.3 复杂度

与边差分类似，预处理 $O(N \log N)$ ，每次更新 $O(1)$ ，一次 DFS $O(N)$ 。

3. 综合 C++17 模板

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

const int MAXN = 200000;
int N, Q;
vector<pair<int,int>> adj[MAXN+1];   // for edge-diff: (to, eid)
vector<int>         adj2[MAXN+1];    // for node-diff: only to
int up[20][MAXN+1], depth[MAXN+1], fa[MAXN+1];
ll diff_arr[MAXN+1];

// --- LCA 预处理 ---
void dfs_lca(int u,int p){
    up[0][u] = p; fa[u] = p;
    for(int v: adj2[u]){
        if(v==p) continue;
        depth[v] = depth[u] + 1;
        dfs_lca(v,u);
    }
}
int lca(int u,int v){
    if(depth[u]<depth[v]) swap(u,v);
    int d = depth[u]-depth[v];
    for(int k=0; k<20; k++)
        if(d>>k &1) u = up[k][u];
    if(u==v) return u;
    for(int k=19; k>=0; k--){
        if(up[k][u]!=up[k][v]){
            u = up[k][u];
            v = up[k][v];
        }
    }
    return up[0][u];
}

// --- 边差分答案数组 ---
ll ans_edge[MAXN+1];
// 边差分用的 DFS
void dfs_edge(int u,int p){
    for(auto [v,eid]: adj[u]){
        if(v==p) continue;
        dfs_edge(v,u);
        diff_arr[u] += diff_arr[v];
        ans_edge[eid] = diff_arr[v];
    }
}

// --- 点差分答案数组 ---
ll ans_node[MAXN+1];
// 点差分用的 DFS
void dfs_node(int u,int p){
    for(int v: adj2[u]){
        if(v==p) continue;
        dfs_node(v,u);
        diff_arr[u] += diff_arr[v];
    }
    ans_node[u] = diff_arr[u];
}

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

    cin >> N;
    // 建图：先读无向树；为边差分和点差分分别存
    for(int i=1;i<N;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
        adj2[u].push_back(v);
        adj2[v].push_back(u);
    }

    // LCA 预处理
    dfs_lca(1,0);
    for(int k=1;k<20;k++){
        for(int v=1;v<=N;v++){
            up[k][v] = up[k-1][ up[k-1][v] ];
        }
    }

    // 选择模式 1=边差分  2=点差分
    int mode;
    cin >> mode >> Q;

    // 处理 Q 次更新
    while(Q--){
        int u,v;
        ll w;
        cin >> u >> v >> w;
        int p = lca(u,v);
        if(mode == 1){
            // 边差分
            diff_arr[u]    += w;
            diff_arr[v]    += w;
            diff_arr[p]    -= 2*w;
        } else {
            // 点差分
            diff_arr[u]   += w;
            diff_arr[v]   += w;
            diff_arr[p]   -= w;
            if(fa[p]) diff_arr[fa[p]] -= w;
        }
    }

    if(mode == 1){
        dfs_edge(1,0);
        // 输出每条边的答案
        for(int i=1;i<N;i++){
            cout << ans_edge[i] << "\n";
        }
    } else {
        dfs_node(1,0);
        // 输出每个节点的答案
        for(int i=1;i<=N;i++){
            cout << ans_node[i] << (i==N?'\n':' ');
        }
    }
    return 0;
}

4. 随机示例验证

边差分

样例树（5 节点，4 条边）：
```
1—2(eid=1), 1—3(eid=2), 2—4(eid=3), 2—5(eid=4)
```
更新：
```
(4,5,+1), (3,4,+2)
```
- 第一次：4→5 的边 +1⇒eid=3,eid=4
- 第二次：3→4 的边 +2⇒eid=2,eid=1,eid=3
  
  最终：
```
eid1=2, eid2=2, eid3=3, eid4=1
```
点差分

同树，更新：
```
(4,5,+1), (3,4,+2)
```
- 第一次：4→5 路径上的节点 {4,2,5} 都 +1
- 第二次：3→4 路径上的节点 {3,1,2,4} 都 +2
  
  合并：
```
node1=2, node2=3, node3=2, node4=3, node5=1
```

总结：

边差分 用于“路径上每条边的批量更新”，diff[u]+=w; diff[v]+=w; diff[lca]-=2w;，DFS 聚合后子树 diff[v] 即是对应边的答案。
点差分 用于“路径上每个节点的批量更新”，在 LCA 处和其父处都要做 $-w$ 抵消，DFS 聚合后 diff[u] 即是节点 $u$ 的答案。