差分/树上差分(雾)
前言
说实话，写这东西挺迷的，按道理说这玩意我应该会，但是做题的时候又不会，跟新学一样，就离谱。
差分这东西就挺神奇的，前后加一减一就能维护区间。开始觉得挺奇怪的，细致一看挺简单。——1Liu
锐评记不清了，全靠当事人记忆。
差分
差分，又名差分函数或差分运算，差分的结果反映了离散量之间的一种变化，是研究离散数学的一种工具，常用函数差近似导数。
差分在数学、物理和信息学中应用很广泛，模拟电路中有差分放大电路一说。差分运算，相应于微分运算。——百度百科
嘛玩意。
思想
差分的核心思想是记录当前位置的数与上一位置的数的差值。
其实可以看做前缀和的逆运算，比如：设数列 \(a\)，差分数组为 \(diff\)，有：$$diff_i = a_i - a_{i - 1}$$
其实我们可以比较一下前缀和和差分：
| 类型/位数 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 原数列 \(a\) | 9 | 4 | 7 | 5 | 9 |
| 前缀和 \(sum\) | 9 | 13 | 20 | 25 | 34 |
| 差分数组 \(diff\) | 9 | -5 | 3 | -2 | 4 |
| 前缀和的差分数组 | 9 | 4 | 7 | 5 | 9 |
| 差分数组的前缀和 | 9 | 4 | 7 | 5 | 9 |
观察到：原数列的前缀和的差分数组还是原数列，原数列的差分数组的前缀和也是原数列，这就是差分被称为前缀和的逆运算的原因。
所以不难得出，\(\sum ^ {n} _ {i = 1} diff_i = a_n\)。
运用
给定一个序列 \(a\)，有若干次修改，\(l,r,data\) 表示 \(i ∈ [l, r],a_i + data\)；
全部修改操作后有若干次询问，求 \(\sum ^ {r} _ {i = l} a_i\)。
考虑差分数组记录的数据，它记录的是当前位置和上一个数的差值。在差分数组 \(diff_l + data\) 同时 \(diff_{r + 1} - data\) 就能达到区间修改的操作。
再把上边那张表拉下来，设给 \(i ∈ [2,4]\) 的 \(a_i\) 都加上 \(5\)，于是这张表就变成了：
| 类型/位数 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 原数列 \(a\) | 9 | 9 | 12 | 10 | 9 |
| 前缀和 \(sum\) | 9 | 18 | 30 | 40 | 49 |
| 差分数组 \(diff\) | 9 | 0 | 3 | -2 | -1 |
| 前缀和的差分数组 | 9 | 9 | 12 | 10 | 9 |
| 差分数组的前缀和 | 9 | 9 | 12 | 10 | 9 |
注意到因为是区间修改，所以 \([2,4]\) 的数大小的相对关系不变，所以 \([2,4]\) 的差分数组不会变。\(a_2\) 变大了 \(5\)，对应 \(diff_2 = a_2 - a_1\) 也变大了 \(5\)。同理 \(a_4\) 变大了 \(5\)，\(diff_5 = a_5 - a_4\) 就减小了 \(5\)。
题
这个真没写过，区间问题一般直接就线段树或者树状数组艹了。
树上差分
其实这个是这篇博客的主要内容，昨天补题的时候发现树上差分我居然不会。
运用
因为差分的思想什么的上边都讲了，直接写用法了。当题目要求对树上一段路径进行操作，并且询问某个点或者某条边被经过的次数时，就可以用树上差分解决。
值得注意的是点差分和边差分并不完全相同。
点差分
将两点 \(u\)，\(v\) 之间路径上的所有点的点权增加 \(x\)，\(anc = LCA(x,y)\)，\(anc\) 的父亲节点为 \(p\)，操作有：
diff[u] += x, diff[v] += x, diff[anc] -= x, diff[p] -= x;。
设原树如下，初始点权均为 \(0\)，令 \(2,4\) 路径上的点权增加 \(3\)。
差分数组 \(diff\) 初始都为 \(0\)。
操作之后：
\(diff_2 = 3, diff_4 = 3, diff_3 = -3, diff_1 = -3\)。
之后 \(dfs\) 向上回溯，设当前节点为 \(u\)，它的儿子为 \(v\)，\(diff_u += diff_v\)，所有儿子都回溯完后的 \(diff_u\) 即为 \(u\) 的权值。
边差分
点差分的时候我们直接以节点编号为下标进行差分，那边差分的时候我们把边像树剖边权转点权一样把边权下放到点，至于直接以边的标号差分......想想就好。
至于怎么转成点权，我们去考虑树的性质，每个节点和它的儿子节点之间有边相连。对于儿子节点，它的父亲是唯一的，所以它如果要到达父亲节点，有且仅有这一条边，换而言之就是这每条边与儿子节点一一对应，所以我们可以直接把点权下放到儿子节点上。
将两点 \(u\)，\(v\) 之间路径上的所有边的边权增加 \(x\)，\(anc = LCA(x,y)\)，操作有：
diff[u] += x, diff[v] += x, diff[anc] -= 2 * x;
同样的例子，只是根节点没有了权值（它找不到对应的边），令 \(2,4\) 路径上的边权增加 \(3\)：
操作后：
（\(LCA\) 的权值代表的边不在路径上）。
\(diff_2 = 3, diff_4 = 3, diff_3 = -6\)。
当我们同样 \(dfs\) 进行一波回溯之后，就能得到当前点对应的边的权值。
题
这回有了，本来写这篇博客的原因好像就是这道题，为了盘醋包了顿饺子了属于是。
P2680 [NOIP2015 提高组] 运输计划
完成阶段性工作的最短时间就是要求最大值的最小值，可以去考虑二分，之后的问题就是如何去写 check 函数了。
贪心的想，对于一个数 \(num\)，我们只需要考虑长度 \(> num\) 的路径，因为长度 \(≤ num\) 的路径减掉一条边长度还是 \(≤ num\) 的，没啥用。然后去考虑减掉什么样的边，这条边一定要对所有 \(> num\) 的路径产生影响，否则即使减掉这条边，仍然有 \(> num\) 的路径存在，就白瞎了。所以，我们可以用树上差分（边差分），记录下每条边被 \(> num\) 的路径覆盖的次数，再选出被所有 \(> num\) 的路径覆盖的边的最大的那条删去，判断此时所有路径是否小于等于 \(num\) 即可。至于如何判断所有路径，直接记录路径的最大值就行了。
Code
点击查看代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 3e5 + 10;
const int INF = 2147483647;
int n, m, cnt, num, h, t, maxn, minn = INF;
int head[MAXN], dis[MAXN], val[MAXN];
int fa[MAXN], son[MAXN], size[MAXN], deep[MAXN];
int dfn[MAXN], top[MAXN];
int diff[MAXN]; //差分数组
struct Edge{
int to, next, dis;
}e[MAXN << 1];
inline void Add(int u, int v, int w){
e[++cnt].to = v;
e[cnt].dis = w;
e[cnt].next = head[u];
head[u] = cnt;
}
struct Line{ //记录每条航线
int x, y, anc, dis;
}l[MAXN];
inline int read(){
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
void dfs_deep(int rt, int father, int depth){
size[rt] = 1;
fa[rt] = father;
deep[rt] = depth;
int max_son = -1;
for(register int i = head[rt]; i; i = e[i].next){
int v = e[i].to;
if(v == father) continue;
val[v] = e[i].dis;
dis[v] = dis[rt] + e[i].dis;
dfs_deep(v, rt, depth + 1);
size[rt] += size[v];
if(max_son < size[v]){
son[rt] = v;
max_son = size[v];
}
}
}
void dfs_top(int rt, int top_fa){
dfn[rt] = ++num;
top[rt] = top_fa;
if(!son[rt]) return;
dfs_top(son[rt], top_fa);
for(register int i = head[rt]; i; i = e[i].next){
int v = e[i].to;
if(!dfn[v]) dfs_top(v, v);
}
}
int Get_LCA(int x, int y){
while(top[x] != top[y]){
if(deep[top[x]] < deep[top[y]]) swap(x, y);
x = fa[top[x]];
}
if(deep[x] > deep[y]) swap(x, y);
return x;
}
void dfs(int rt){
for(register int i = head[rt]; i; i = e[i].next){
int v = e[i].to;
if(v == fa[rt]) continue;
dfs(v);
diff[rt] += diff[v];
}
}
bool Check(int num){
int sum = 0, maxval = 0;
memset(diff, 0, sizeof(diff));
for(register int i = 1; i <= m; i++){
if(l[i].dis > num){
++diff[l[i].x];
++diff[l[i].y];
diff[l[i].anc] -= 2;
++sum;
}
}
dfs(1);
for(register int i = 1; i <= n; i++)
if(diff[i] == sum) maxval = max(maxval, val[i]);
if(maxn - maxval <= num) return true;
else return false;
}
int Lower_Bound(int l, int r){
int ans;
while(l <= r){
int mid = (l + r) >> 1;
if(Check(mid)){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
int main(){
n = read(), m = read();
for(register int i = 1; i <= n - 1; i++){
int u, v, w;
u = read(), v = read(), w = read();
Add(u, v, w), Add(v, u, w);
minn = min(minn, w);
}
dfs_deep(1, 0, 1);
dfs_top(1, 1);
for(register int i = 1; i <= m; i++){
l[i].x = read(), l[i].y = read();
l[i].anc = Get_LCA(l[i].x, l[i].y);
l[i].dis = dis[l[i].x] + dis[l[i].y] - 2 * dis[l[i].anc];
maxn = max(maxn, l[i].dis);
}
h = minn, t = maxn;
printf("%d", Lower_Bound(h, t));
return 0;
}