树上差分NOIP

💡 核心思想

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

🎯 直觉理解

树上差分是"在树上做区间修改、最后查一次"的工具，和数组差分思路一脉相承。

点差分：给路径 u→v 上所有点加 1，只需 $diff[u]+=1, diff[v]+=1, diff[lca]-=1, diff[fa[lca]]-=1$，最后 DFS 从下往上累加子树和即可还原。

边差分：把边权记到深度较深的点上，公式变成 $diff[u]+=1, diff[v]+=1, diff[lca]-=2$。典型应用：统计每条边/点被多少条路径覆盖（如"运输计划"类题）。关键是把"路径修改"翻译成四个点的差分操作——这个翻译想通，树上差分就通了。

📝 算法流程

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;
}

⚠️ 常见坑点

📚 相关题目