差分、树上差分

定义：差分就是数组中每一项都与前一项做差，最后得出的序列。
例如：数组：2,5,3,7,2,3
差分后的序列：2,3,-2,4,-5,1,-3
注意：第一个数与原数组相同，相当于2-0；最后一个数与原数组互为相反数，相当于0-3；
差分的性质：
1.差分序列的前缀和就是原数组；
2.将原数组在[L,R]区间上的数全部加1，相当于让差分数组在L处+1，在R+1处-1；

考虑差分的一个应用：

图片来源：https://blog.csdn.net/a135193...

树上差分的两种思路：

1.找被所有路径共同覆盖的边。
例题：洛谷：https://www.luogu.com.cn/prob...
分析见代码：

//1.找被所有路径共同覆盖的边。
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>

using namespace std;
const int N = 300010;
int fa[N][26];
int depth[N], dist[N];
int tmp[N], pre[N];
int cnt,flag;
//tmp存节点出现的次数，即节点与节点父亲的边在所有路径中出现的次数
//pre存节点与节点父亲之间的边，本题中存的是边权，别的题中也有可能存编号
int n, m;
struct node
{
    int s, t;
    int lca;
} path[N];
int head[N], nex[2 * N], val[2 * N], to[2 * N], idx;
int u, v, w;
void add(int u, int v, int w)
{
    to[idx] = v;
    val[idx] = w;
    nex[idx] = head[u];
    head[u] = idx++;
}
int que[N];

void bfs(int root)
{
    memset(depth, 0x3f, sizeof(depth));
    depth[0]=0;
    depth[root] = 1;
    int h = 0, t = 0;
    que[t++] = root;
    while (h != t)
    {
        int top = que[h++];
        for (int i = head[top]; ~i; i = nex[i])
        {
            int j = to[i];
            int w = val[i];
            if (depth[j] > depth[top] + 1)
            {
                depth[j] = depth[top] + 1;
                dist[j] = dist[top] + val[i];
                que[t++] = j;
                pre[j] = val[i];
                fa[j][0] = top;
                for (int k = 1; k <=21; k ++)
                {
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
                }
            }
        }
    }
}

int get_lca(int u, int v)
{
    if (depth[u] < depth[v])
    {
        swap(u, v);
    }
    //第一步：先让u跳到与v同一高度
    for (int i = 21; i >= 0; i--)
    {
        if (depth[fa[u][i]] >= depth[v])
        {
            u = fa[u][i];
        }
    }

    if (u == v) //特殊情况，u和v调到同一高度之后重合，只需返回u或v即可
    {
        return u;
    }
    //第二步，让u和v跳到最近公共祖先的下一层
    for (int i = 21; i >= 0; i--)
    {
        if (fa[u][i] != fa[v][i])
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0]; //再向上跳一步就是root
}

int judge(int a,int f,int cnt,int maxn)
{
    for(int i=head[a];~i;i=nex[i])
    {
        int j=to[i];
        if(j==f)
        {
            continue;
        }
        tmp[a]+=judge(j,a,cnt,maxn);
    }
    if(tmp[a]==cnt&&pre[a]>=maxn)
    {
        flag=1;
    }
    return tmp[a];
}

bool check(int x)
{
    memset(tmp, 0, sizeof(tmp));
    cnt = 0,flag=0;
    int maxn = 0;
    for (int i = 1; i <= m; i++)
    {
        int dis = dist[path[i].s] + dist[path[i].t] - 2 * dist[path[i].lca];
        if (dis > x)
        {
            cnt++;
            maxn = max(maxn, dis - x);
            //s,t加一，最近公共祖先-2
            tmp[path[i].s]++;
            tmp[path[i].t]++;
            tmp[path[i].lca] -= 2;
        }
    }
    if (!cnt)
    {
        return true;
    }
    judge(1,0,cnt,maxn);
    if(flag)
    {
        return true;
    }
    return false;
}

int main()
{
    scanf("%d %d", &n, &m);
    memset(head, -1, sizeof(head));
    for (int i = 0; i < n - 1; i++)
    {
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }
    bfs(1);

    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d", &path[i].s, &path[i].t);
        path[i].lca = get_lca(path[i].s, path[i].t);
    }
    //二分找正确答案
    long long int l = 0, r = 3000000000;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << l << endl;

    return 0;
}

2.将路径上的所有点权值加一，求最后点的权值。
第二种基本思想见另一篇文章：
https://segmentfault.com/a/11...

拾柒

差分、树上差分

树上差分的两种思路：