这道题目让我们来详细讲一讲树上差分吧。

前置知识

算法介绍

解决问题类型

在一棵树上有两个点

u

和

v

，每个点都有自己的点权，需要把在

u

到

v

的这条简单路径上包含的所有的点的点权同时加上

z

或者减少

z

。

这就是树上差分主要解决的问题。

实现

容易想到暴力，但是这样暴力修改点权的时间复杂度过高，所以不可取，这下，树上差分就派上用场了（别说什么线段树，树状数组，我不会）。

首先，能写到这题的人肯定已经学会了差分，如果不会请移步模板题。

这里的差分实现主要用图片来解释。

有这么一棵树（每个点旁边的数代表这个点的点权）：

现在接到任务，要把

4

到

8

的简单路径上的所有点（包含

4

和

8

）的点权加

1

，问现在每个点的点权。

记

cf_i

为点

i

与点

i-1

的点权差值。

我们先将

4

到根结点，

8

到根结点中的点的点权全部加

1

，用代码来表示为：

CPP

cf[u]++;
cf[v]++;

修改完的结果如下：

我们发现，结果并不是很理想。
问题出在这么几个地方：

$4$ 和 $8$ 的最近公共祖先，也就是 $3$ ，点权多了 $1$ 。
$3$ 的所有祖先结点的点权都多了 $2$ 。

我们先试着解决第一个问题，想到的方法是从

3

开始，先把到后面的所有点的点权减去

1

，用代码表示为：

CPP

int lc = lca(u, v);
//lc存储u和v的最近公共祖先
cf[lc]--;

修改完后：

可以发现，第一个问题已经解决了，此时还剩下的问题：

$3$ 的所有祖先结点的点权都多了 $1$ 。

那么我们如法炮制，从

3

的父亲开始，把到后面的所有点的点权减去

1

，用代码表示为：

CPP

int lc = lca(u, v);
//f[i][j] 表示点i往上跳2^j次会到哪
cf[f[lc][0]]--;

现在修改完后变成了这样：

最后就是这样：

现在是不是没有问题了，那么恭喜你~~被我恭喜到了~~学会了树上差分！

树上差分的优点

在实现上，简单，方便。
在时间上，时间复杂度低，每次修改复杂度为

O(1)

。

树上差分的注意事项

要用差分数组来求出原序列时，可以用搜索的方法。
设点

x

的孩子为

y

，则求出

cf_x

的代码为：

CPP

cf[x] = cf[x] + cf[y];

需要注意：这一部分代码应该写在搜索的回溯时，要等

cf_y

更新完了才能求出正确的

cf_x

。

树上差分例题

P3128
P3258

切入正题

这道题目想让我们干什么？其实就是把

u

到

v

的路径上的点的点权增加

1

。

不过，需要注意的是，一个点

x

可能既能作为上次参观的终点，也可能是下次参观的起点，需要避免重复。
并且，最后一个房间不用给糖果。

学会了树上差分，这题就很简单了。

代码

终于要结束了（相信你们也看累了）。
最近公共祖先的部分就不打注释了，不会的见模板题。

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, dq[N], cf[N], cg[N], dep[N], f[N][18], lg[N], maxd, maxdq = -1;
vector <int> ed[N];
void dfs(int x, int fa){
	dep[x] = dep[fa] + 1;
	f[x][0] = fa;
	if(dep[x] > maxd) maxd = dep[x];
	for(int i = 0;i < ed[x].size();i++){
		int tod = ed[x][i];
		if(tod != fa){
			dfs(tod, x);
			cf[x] += cf[tod];
		}
	}
}
void qcf(int x, int fa){
	for(int i = 0;i < ed[x].size();i++){
		int tod = ed[x][i];
		if(tod != fa){
			dfs(tod, x);
			cf[x] += cf[tod];
		}
	}
}
int lca(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	while(dep[u] > dep[v]){
		u = f[u][lg[dep[u] - dep[v]]];
	}
	if(u == v) return u;
	for(int i = lg[dep[u] - 1];i >= 0;i--){
		if(f[u][i] != f[v][i]){
			u = f[u][i], v = f[v][i];
		}
	}
	return f[u][0];
}
int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i++){
		scanf("%d", &cg[i]);
	}
	for(int i = 1;i < n;i++){
		int x, y;
		scanf("%d%d", &x, &y);
		ed[x].push_back(y);
		ed[y].push_back(x);
	}
	dfs(1, 0);
	for(int i = 2;i <= n;i++) lg[i] = lg[i / 2] + 1;
	for(int j = 1;j <= lg[maxd];j++){
		for(int i = 1;i <= n;i++){
			f[i][j] = f[f[i][j - 1]][j - 1];
		}
	}
	//树上差分的部分 
	for(int i = 1;i < n;i++){
		int x = cg[i], y = cg[i + 1], lc;
		lc = lca(x, y);
		cf[x]++, cf[y]++;
		cf[lc]--, cf[f[lc][0]]--;
	}
	qcf(1, 0);
	//要注意避免重复 
	for(int i = 2;i <= n;i++){
		cf[cg[i]]--;
	}
	for(int i = 1;i <= n;i++){
		printf("%d\n", cf[i]);
	}
	return 0;
}

题解：P3258 [JLOI2014] 松鼠的新家

文章操作