树上差分CSP-S

💡 核心思想

树上差分是处理"树上路径统计"问题的技巧。对于路径 u→v，可以拆分为 u→root + v→root - 2×lca→root。通过对节点进行差分标记（u 和 v 处 +1，lca 和 lca 的父节点处 -1），最后一次 DFS 求子树和即可得到每个节点被经过的次数。

🎯 直觉理解

想象你在树上撒面包屑：从 u 走到 v，你在 u 和 v 各放一袋面包屑，在它们的最近公共祖先 lca 处拿走两袋（因为 u→lca 和 v→lca 的面包屑在 lca 处重叠了）。然后让所有面包屑顺着树往下流，每个节点最终收到的面包屑数量就是它所在路径的数量。

📝 算法流程

1. 预处理 LCA（倍增或 Tarjan）
2. 对于每条路径 (u, v)：diff[u]++, diff[v]++, diff[lca]--, diff[fa[lca]]--
3. 从根节点开始 DFS，求子树和：sum[u] = diff[u] + Σ sum[v]（v 是 u 的子节点）
4. sum[u] 即为经过节点 u 的路径数
5. 若统计边，则将标记放在边上，最后看子节点向父节点的边

$$\text{路径 }u \to v: \quad diff[u]++,\ diff[v]++,\ diff[lca]-=2,\ diff[fa[lca]] \text{（可选）}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

const int N = 100005;
vector g[N];
int diff[N], ans[N];

void dfs(int u, int f) {
    for (int v : g[u]) {
        if (v == f) continue;
        dfs(v, u);
        diff[u] += diff[v]; // 子树和累加到父节点
    }
    ans[u] = diff[u];
}

int main() {
    int n = 5;
    g[1].push_back(2); g[2].push_back(1);
    g[1].push_back(3); g[3].push_back(1);
    g[2].push_back(4); g[4].push_back(2);
    g[2].push_back(5); g[5].push_back(2);
    
    // 路径 4->5：lca=2
    diff[4]++; diff[5]++; diff[2] -= 2;
    
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        cout << "节点 " << i << " 被 " << ans[i] << " 条路径覆盖" << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目