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