关于树形结构:差分树上差分

什么是差分？

定义：差分就是数组中每一项都与前一项做差，最初得出的序列。
例如：数组：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;
}

什么是差分？

树上差分

树上差分的两种思路：