很早以前就搞了当时没写, 因为当时从来不写…😭

树上差分:顾名思义就是 树上面的差分

树上差分擅长在树上一调路径上统计边或者点的信息

按边差分

将a到b的路径上的边权加v

int p = lca(a, b);
d[a] += v, d[p] -= v
d[b] += v, d[p] -= v;

按点的差分

将a到b的路径上的点权加v

int p = lca(a, b);
d[a] += v, d[p] -= v;
d[b] += v, d[fa(p)] -= v;

例题

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

typedef pair<int, int> PII;

const int N = 1e5 + 10, M = 2e5 + 10, K = 20;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][K];
PII g[N];
int d[N];
int id[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);

    depth[0] = 0;
    depth[root] = 1;

    queue<int> q;

    q.push(root);

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];

            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;

                q.push(j);

                fa[j][0] = t;

                for (int k = 1; k <= 17; k++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);

    for (int i = 17; i >= 0; i--)
        if (depth[fa[a][i]] >= depth[b]) a = fa[a][i];

    if (a == b) return a;

    for (int i = 17; i >= 0; i--)
        if (fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }

    return fa[a][0];
}


void dfs(int u, int p)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (j != p)
        {
            dfs(j, u);

            d[u] += d[j];
        }
    }
}

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

    int n;
    cin >> n;

    memset(h, -1, sizeof h);

    int x, y;
    for (int i = 1; i < n; i++)
    {
        cin >> x >> y;

        add(x, y);
        add(y, x);

        g[i] = {x, y};
    }

    bfs(1);

    int m;
    cin >> m;

    while (m--)
    {
        cin >> x >> y;

        d[x]++, d[y]++;
        d[lca(x, y)] -= 2;
    }

    dfs(1, 0);

    for (int i = 1; i < n; i++)
        if (depth[g[i].first] > depth[g[i].second]) id[i] = g[i].first;
        else id[i] = g[i].second;

    for (int i = 1; i < n; i++) cout << d[id[i]] << ' ';


    return 0;
}

P2680 [NOIP2015 提高组] 运输计划

题意: 给定n个点n-1条边的树, 有边权有m条路径, 可以将1条边的权值改为0, 求修改后的最长路径的最短距离是多少.

分析:

1. 最长路径可能不止一条，那么删除的边权就可能不是最长路径的最大边权。

2. 为了使得最长路径能够变小，删除的边权应该在某一些路径的公共边上。

3. 运输计划的完成时间ans的单调性是显而易见的，考虑通过二分答案转为验证。

4. 二分的范围是[0, 3e8]，假设二分的中间值mid为完成时间，枚举m条路径，筛选出超过mid的路径，假设共有cnt条。

5. 对于cnt条超出mid的路径，寻找最大的公共边权，使用“虫洞”方法，若使用后cnt条路径中的最长距离缩小到mid以内，则mid可行，否则不可行。

6. 对于cnt条路径，利用树上差分，统计每条边被覆盖的次数，跑树上前缀和后枚举n-1条边，凡是被覆盖cnt次的都是公共边，维护其中的最大边权mw。

7. 预处理m条路径的距离；

$O(m \times \log n + \log T \times (m + n))$