c++基础树上问题————树上差分：万字泣血！超强解析，一篇就会，无需多言，适合小白，附有例题加强训练！
详细解释c++的树上差分问题，适合参加算法比赛的同学！
目录
注：本文题目均来自蓝桥杯官网公开题目，仅用于技术讨论和算法学习。
用于解决树上的“简单路径”的权值和的修改与查询问题，可以实现“先修改，后查询”的功能
类比于之前学的前缀和还有差分，只是转移到树上
树上差分不支持“边修改边查询”---->树链剖分支持
就是当题目涉及到简单路径时，就可以考虑树上差分！
一，树上点差分
方法：将树形结构线性化，就是将一条链上的信息转化为多链上的信息的组合
如图：
1
|
2
|
4
/ | \
5 6 9
|
12
假设要求(5,12)简单路径的点的权值之和，如果有prefix[i]表示节点i到根的链的权值之和
图中是1到i，这个结果可以表示为prefix[5]+prefix[12]-prefix[4]-prefix[2]。
因为由图，我们想要得到的路径是5-->4-->9-->12,要减去1,2,4上多走的几步。
1.前缀和定义：prefix[x]表示节点x到根这条链上所有节点的权值之和
由树形dp，prefix[x]=prefix[fa[x]]+a[x] （注：fa[x]:the father of x），路径(u,v)的权值之和=prefix[u]+prefix[v]-prefix[lca]-prefix[fa[lca]]（注： lca:最近公共祖先）。
2.差分定义：diff[i]表示节点i到根的这条链上，自底向上的点的差分，将diff[i]加上x，意味着把这条链（从下往上）的所有点的权值都加上x，操作完成后自底向上做前缀和即可还原数组
用树形dp的方法，令a[x]=diff[x]+diff[所有儿子节点]即可，还存在一种特殊的差分，他不是自底向上的，而是自顶向下的，用于每次修改一颗子树，这需要将差分和前缀和方向进行翻转，不是传统意义上的树上差分。
二，树上边差分
如图：
1
|
2
|
|x
|
4
/ | \
5 6 9
|
12 在树上，除根节点外，每个点都有唯一对应的父亲边，于是可以用子节点编号来表示边编号
如图中a[4]=x,即边(2,4)的权值， 树中每个节点 i（除根节点外）都有一条唯一的父边 (i, fa[i])（连接 i 和其父节点 fa[i]）。
a[i] 的值恰好等于 所有查询路径中经过这条父边(i, fa[i]) 的次数。
1.前缀和的定义：。。。。。。。表示所有边的权值之和，路径(u,v)的权值之和：prefix[u]+prefix[v]-prefix[lca]。
2.差分定义：diff[i]表示节点i到根的这条链上，自底向上边的差分，将diff[i]加上x，意味着把这条链（从下往上）的所有点的权值都加上x，操作完成后自底向上做前缀和即可还原为原数组
三，例题详解
例题1：23年蓝桥杯真题 砍树
问题描述
给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1,b1)，(a2,b2)，...，(am,bm)，其中 ai 互不相同，bi 互不相同，ai，bj (1≤i,j≤m)(1≤i,j≤m)。小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai,bi) 满足 ai 和 bi 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 开始），否则输出 −1。
输入格式
输入共 n+m 行，第一行为两个正整数 n，m。后面 n−1 行，每行两个正整数 xi，yi 表示第 i 条边的两个端点。后面 m 行，每行两个正整数 ai，bi。
输出格式
一行一个整数，表示答案，如有多个答案，输出编号最大的一个。
样例输入
6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5
样例输出
4
样例说明
断开第 2 条边后形成两个连通块：3,4，1,2,5,6，满足 3 和 6 不连通，4 和 5 不连通。断开第 4 条边后形成两个连通块：1,2,3,4，5,6，同样满足 3 和 6 不连通，4 和 5 不连通。4 编号更大，因此答案为 4。
评测用例规模与约定
对于 30%的数据，保证 1<n≤1000。
对于 100% 的数据，保证 1<n≤10^5，1≤m≤n/2。
思路简析：
这道题非常难（个人觉得），需要合理转换思路，还要熟练多种算法方法比如并查集，求lca，dfs等等。
思路：断开所求2个节点之间的简单路径的任意边，则二者必然分开
转换思想：先在一棵树上找到查询节点对（有m个节点对）的简单路径，依次将路径的每条边权值加一，将所有（也就是m个）待查询节点对都进行边权值加一操作后，看看有那一条边的权值等于m，则选择这条边砍断必然会使得所有查询节点对分开。
比如上述题目提供了两个节点对(3,6),(4,5)，将二者的简单路径上边的权值都加上1（初始均为0），发现权值加1后边2和边4的权值为2，也就是m，则断开这两条边的任意一条边就可以实现这两组节点对都分开。但是要选择编号大的4号边。
所以题目就转换为了查看权值的问题！
若有多条边权值是m则选择编号最大的那个，若无合适边则输出-1
代码逐步详解：
方法1：标准满分方法
1，纯代码版本，无注释解析，大家可以先预览
#include<utility>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<bitset>
using namespace std;
using ll=long long;
const int N=1e5+9;
ll pre[N],fa[N];
vector<int>g[N];
ll diff[N],a[N];
map<int,int>mp[N];
map<int,int>lca[N];
bitset<N>vis;
vector<pair<int,int>>ques;
vector<int>vec[N];//记录需要做lca的点对
int root(int x)
{
return pre[x]=(pre[x]==x?x:root(pre[x]));
}
void tarjan(int x,int father)
{
fa[x]=father;
for(const auto&y:g[x])
{
if(y==fa[x]) continue;
tarjan(y,x);
pre[root(y)]=root(x);
}
vis[x]=true;
for(const auto&y:vec[x])
{
if(vis[y]) lca[x][y]=lca[y][x]=root(y);
}
}
void dfs(int x)
{
a[x]=diff[x];
for(const auto &y:g[x])
{
if(y==fa[x]) continue;
dfs(y);
a[x]+=a[y];
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;cin>>n>>m;
//构建无向图，并记录编号
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
g[u].push_back(v),g[v].push_back(u);
mp[u][v]=mp[v][u]=i;
}
//输入查找节点
for(int i=1;i<=m;i++)
{
int x,y;cin>>x>>y;
ques.push_back({x,y});
vec[x].push_back(y),vec[y].push_back(x);
}
//预处理并查集
for(int i=1;i<=n;i++) pre[i]=i;
//求lca
tarjan(1,0);
//进行差分和还原操作，计算边权！！！
for(const auto&t:ques)
{
int u=t.first,v=t.second;
diff[u]++,diff[v]++,diff[lca[u][v]]-=2;
}
dfs(1);
//最后输出答案
int ans=-1;
for(int i=1;i<=n;i++)
{
if(a[i]==m) ans=max(ans,mp[i][fa[i]]);
}
cout<<ans<<'\n';
return 0;
}2，有注释版本，详细解析！
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
using ll = long long;
ll diff[N], a[N];
vector<int>g[N];
int fa[N], pre[N];
//路径压缩
int root(int x)
{
return pre[x] = (pre[x] == x ? x : root(pre[x]));
}
vector<int>vec[N]; // 记录需要做lca的点对，就是1到m的查询点
bitset<N>vis; // 标记节点是否被访问过
map<int, int>lca[N]; // 存储点对的lca结果
/*vis 是一个 bitset，用于标记节点是否已完成所有子树的遍历（即「回溯完成」）。
只有当节点的所有子节点都处理完毕后，才会标记为 true。*/
void tarjan(int x, int father)// Tarjan算法求LCA
{
fa[x] = father;
//这一步是在遍历x的所有子节点，及子节点的子节点
for (const auto& y : g[x])
{
if (y == fa[x])continue;
tarjan(y, x);
pre[root(y)] = root(x);
/*当子节点 y 的所有子树都处理完毕后，执行 pre[root(y)] = root(x)：
将 y 所在集合的根节点（root(y)）合并到 x 所在集合的根节点（root(x)）中。
这一步的作用是：标记 y 及其子树已处理完毕，并将它们归入 x 的集合，为后续计算 LCA 做准备。*/
//y是x的子节点，y的根有可能就是x，所以可将y集合并入x集合中
}
vis[x] = true;//说明x已经查询过了
for (const auto& y : vec[x])//处理与x有关的查询，比如我要查询3,5是否有公共祖先，y就是5，x就是3
{
if (vis[y])lca[x][y] = lca[y][x] = root(y);//若y也被查询过，说明在之前遍历x及其子树的过程中
//y出现过了
//则y与x必然联通，二者必然有lca！
/*此时 root(y) 之所以是 LCA，原因如下：
y 已处理完毕，意味着 y 的所有祖先（包括 LCA）都已完成合并，
root(y) 指向 y 所在分支中最深的已合并祖先。
x 正在处理中（尚未合并到父节点），而 y 已处理，说明 x 和 y 的公共祖先中，
最深的那个就是 root(y)（因为 y 已合并到该祖先的集合中，而 x 还未继续向上合并）。*/
}
}
void dfs(int x)// 深度优先搜索计算对于树中任意节点 i（非根节点），
//a[i] 最终的值等于所有查询路径中经过边 (i, fa[i]) 的数量（fa[i] 是 i 的父节点）。
{
a[x] = diff[x];
for (const auto& y : g[x])
{
if (y == fa[x])continue;
dfs(y);
a[x] += a[y];// 将子节点的a值累加到当前节点
//离根越近的节点经过的次数越多，所以是a[x]+=a[y]
}
}
map<int, int>mp[N];// 存储边的编号，用于查询边的编号
int main()
{
int n, m; cin >> n >> m;
//构建无向图
for (int i = 1; i < n; i++)
{
int u, v; cin >> u >> v;
g[u].push_back(v), g[v].push_back(u);
//为每条边编号
mp[u][v] = mp[v][u] = i;//这里u和v一定是父子关系
}
//输入要查找的两个节点
vector<pair<int, int>>ques;
for (int i = 1; i <= m; i++)
{
int u, v; cin >> u >> v;
ques.push_back({ u,v });
vec[u].push_back(v), vec[v].push_back(u);
}
//求lca
for (int i = 1; i <= n; i++)
{
pre[i] = i;// 每个节点的父节点初始化为自身
}
tarjan(1, 0);
//差分
//解决「统计每条边被多少查询路径经过」的关键技巧
for (const auto& t : ques)
{
int u = t.first, v = t.second;// 获取查询的两个节点
//在这段代码中，t 是一个循环变量，是一个临时变量，
// 代表 ques 容器中的每个查询对象
/*ques 是一个存储查询的向量（vector<pair<int, int>> ques），
其中每个元素都是一个 pair<int, int> 类型的对象，
表示一个查询的两个节点（u, v）。
for(const auto&t:ques) 是 C++11 引入的范围 for 循环（也叫 foreach 循环），
用于遍历 ques 中的所有元素。循环中，t 会依次代表 ques 中的每个 pair<int, int> 对象。*/
diff[u]++, diff[v]++, diff[lca[u][v]] -= 2;// 执行差分操作
//这一句话的意思就是只将u->v的简单路径上的权值加一！！！
//对应边权[i,fa[i]]-->即a[i]=diff[i]+a[i+1]
}
/*c++17绑定语法，但蓝桥杯不支持，可以这么写:
for(const auto &[u,v]:ques)
{
diff[u]++, diff[v]++, diff[lca[u][v]] -= 2;
} */
/*diff[u]++ 和 diff[v]++：
给路径的两个端点 u 和 v 各加 1，标记「路径从这两个点开始向上延伸」。
diff[lca[u][v]] -= 2：
给 u 和 v 的 LCA（记为 l）减 2，用于抵消「u 到 l」和「v 到 l」在 l 处的重复计数。
原因是：u 到 l 的路径和 v 到 l 的路径在 l 处汇合，
而 l 本身不属于路径 (u, v) 的边（边是 l 与其子节点之间的），因此需要减去多算的 2 次。*/
//a[i] 的值恰好等于 所有查询路径中经过这条父边 (i, fa[i]) 的次数。
//例子：
/*假设有树 1-2-3，查询路径 (3, 1)，其 LCA 是 1：
执行差分：是自下而上的diff[3]++，diff[1]++，diff[1] -= 2 → 最终 diff[3] = 1，diff[1] = -1。
执行 dfs 计算 a：
a[3] = diff[3] = 1（边 (3, 2) 被经过 1 次）。
a[2] = diff[2] + a[3] = 0 + 1 = 1（边 (2, 1) 被经过 1 次）。
a[1] = diff[1] + a[2] = -1 + 1 = 0。
这与实际情况一致：路径 (3, 1) 经过边 (3, 2) 和 (2, 1)，每条边的计数都是 1。*/
//还原
dfs(1);// 调用DFS计算子树和，还原差分结果
//代码中的 dfs(1); 被注释为「还原」，其实际作用是通过深度优先搜索，
//将 diff 数组的差分标记 “还原” 为每条边被查询路径经过的实际次数，存储在 a 数组中。
int ans = -1;//这段代码是求解问题的最终步骤，
//用于从所有边中找到「被所有查询路径都经过」且「编号最大」的边。
// 初始化答案为-1（若没有符合条
// 件的边，最终会输出-1）
for (int i = 1; i <= n; i++)
{ // 遍历所有节点与其父节点所构成的边，根节点也有一条虚边
if (a[i] == m)
{ // 核心判断：若a[i]等于查询总数m
// 更新答案为“当前边编号”和“已有最大编号”中的较大值
ans = max(ans, mp[i][fa[i]]);
}
}
cout << ans << '\n';
return 0;
}方法二：暴力解法，但是部分测试用例会超时，只能拿部分分
///////////////////砍树题方法2：暴力解法（更加简单直观）
//时间复杂度较高：对于每条路径都进行一次 DFS，在最坏情况下时间复杂度为 O (m*n)
//所以此方法超时了
#include<bits/stdc++.h>
using namespace std;
//思路：删除m个路径的公共边
//如何找到公共边：通过dfs/bfs找到两个点之间的路径，给这
//条路径打上标记，如果一条边有m个标记，就说明这条边是m个路径上的公共边
//即可以作为答案的参考范围
using ll = long long;
const int N = 1e5 + 9;
typedef pair<int, int>pii;
vector<int>g[N];
int n, m;
int w[N];//记录每一条边的边权
map<pii, int>id;
bool dfs(int u, int s, int fa, int v)//表示路径u-->v,s是当前走到的点，fa：父节点
{
if (s == v)return true;//如果当前点就是终点，说明已经走完
for (int i = 0; i < g[s].size(); i++)
// for(const auto&i:g[s])。没有正确获取子节点。
// 这一句表示i是s的子节点，也就是son
// 变量名使用不当：如果依然用 i 作为循环变量（如 for(const auto&i:g[s])），
// 然后在后续代码中继续写 g[s][i]，就会导致错误（因为 i 已经是子节点值，而非索引）。
// 对范围 for 的理解偏差：范围 for 循环直接迭代容器中的元素值，而不是索引。
// 原代码需要的是 g[s] 中的元素（子节点），所以循环变量应该直接表示子节点，而不是用索引去二次访问。
// 在 C++ 中，vector 容器的索引是从 0 开始的（零基索引），
// 这是 C++ 中所有标准容器（如 vector、array 等）以及原生数组的通用约定。
// 所以不能从1开始
{
int son = g[s][i];
if (son == fa)continue;
if (dfs(u, son, s, v))
{
int ID = id[{s, son}];
w[ID]++;
return true;
}
}
return false;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i < n; i++)
{
int x, y; cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
id[{x, y}] = id[{y, x}] = i;
}
for (int i = 1; i <= m; i++)
{
int x, y; cin >> x >> y;
dfs(x, x, -1, y);
//对于起始节点 x 来说，它是路径的起点，没有父节点，
//因此需要用一个不可能作为节点编号的值来表示 “无父节点”。
//使用 -1 作为初始父节点，可以明确区分于正常的节点编号（1~n），确保不会与任何有效节点冲突。
}
int ans = -1;
//从高位编号遍历
for (int i = n; i >= 1; i--)
{
if (w[i] == m)
{
ans = i;
break;
}
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}
//////////////////若要改变成const auto 形式：
for(const auto& son : g[s]) // 直接遍历子节点，变量名应该是son而不是i
{
if(son == fa) continue; // 现在son就是当前子节点，无需再通过索引获取
if(dfs(u, son, s, v))
{
int ID=id[{s, son}]; // 直接使用son
w[ID]++;
return true;
}
}例题2：蓝桥杯官网——零食采购
问题描述
小蓝准备去星际旅行，出发前想在本星系采购一些零食，星系内有 n 颗星球，由 n−1 条航路连接为连通图，第 i 颗星球卖第 ci 种零食特产。小蓝想出了 q 个采购方案，第 i 个方案的起点为星球 si，终点为星球 ti，对于每种采购方案，小蓝将从起点走最短的航路到终点，并且可以购买所有经过的星球上的零食（包括起点终点），请计算每种采购方案最多能买多少种不同的零食。
输入格式
输入的第一行包含两个正整数 n,q，用一个空格分隔。
第二行包含 n 个整数 c1,c2,⋯,cn，相邻整数之间使用一个空格分隔。
接下来 n−1 行，第 i 行包含两个整数 ui,vi，用一个空格分隔，表示一条航路将星球 ui 与 vi 相连。
接下来 q 行，第 i 行包含两个整数 si,ti，用一个空格分隔，表示一个采购方案。
输出格式
输出 q 行,每行包含一个整数,依次表示每个采购方案的答案。
样例输入
4 2
1 2 3 1
1 2
1 3
2 4
4 3
1 4
样例输出
3
2
样例说明
第一个方案路线为 {4,2,1,3}，可以买到第 1,2,3 种零食;
第二个方案路线为{1,2,4}，可以买到第 1,2 种零食。
评测用例规模与约定
对于 20% 的评测用例，1≤n,q≤5000；
对于所有评测用例，1≤n,q≤10^5,1≤ci≤20,1≤ui,vi≤n,1≤si,ti≤n。
思路简析：
这里运用前缀和来判定，需要的是“查询”而不是“修改”
令prefix[x][i]表示x------>根上卖i第种零食的星球个数
方法和上面相同，最后判断prefix[u][i] + prefix[v][i] - prefix[_lca][i] - prefix[fa[_lca]][i]即可
详细解析见代码：
#include <iostream>
#include<utility>
#include<vector>
#include<map>
#include<algorithm>
#include<bitset>
using namespace std;
using ll=long long;
const int N=1e5+9;
ll prefix[N][21],c[N],pre[N],fa[N];
vector<int>g[N];
map<int,int>lca[N];
vector<int>vec[N];//记录查询点对，用于求lca
bitset<N>vis;
vector<pair<int,int>>ques;//也是记录点对，用于前缀和/差分
//prefix[x][i]表示星球x到根的含有第i种零食的总数量
int root(int x)
{
return pre[x]=(pre[x]==x?x:root(pre[x]));
}
void tarjan(int x,int father)
{
fa[x]=father;
for(const auto&y:g[x])
{
if(y==fa[x]) continue;
tarjan(y,x);
pre[root(y)]=root(x);
}
//将x标记为已处理
vis[x]=true;
for(const auto&y:vec[x])
{
if(vis[y]) lca[x][y]=lca[y][x]=root(y);
}
}
//这段dfs的核心作用，就是计算所有节点到第x为根的根节点的路径上所有零食出现的次数！
/*
这段 dfs 函数的核心作用是计算从根节点到每个节点的路径上，每种颜色出现的次数，为后续计算任意路径的颜色种类做准备。我们一步步拆解来看：
1. 函数作用
假设树的根节点是 1（因为 main 函数中调用 dfs(1)），dfs(x) 会递归遍历以 x 为根的子树，计算并存储 从根节点到 x 的路径上 每种颜色（颜色范围是 1~20）出现的次数，结果存在 prefix[x][i] 中。
2. 逐行解析
for(int i=1;i<=20;i++)
{
prefix[x][i] = prefix[fa[x]][i];
}
fa[x] 是 x 的父节点（在 tarjan 函数中已经记录了每个节点的父节点）。
这行代码的意思是：先把父节点到根的颜色计数，复制给当前节点 x。
因为从根到 x 的路径，本质上是 “从根到父节点 fa[x] 的路径” 再加上 x 本身，所以先继承父节点的计数结果。
prefix[x][c[x]]++;
c[x] 是节点 x 自己的颜色。
这行代码的意思是：在继承父节点计数的基础上，给当前节点的颜色加 1。
因为 x 本身的颜色也属于 “根到 x 的路径” 的一部分，所以需要在父节点的基础上递增。
*/
void dfs(int x)
{
//先将x父节点的情况复制给自己
for(int i=1;i<=20;i++) prefix[x][i]=prefix[fa[x]][i];
prefix[x][c[x]]++;
for(const auto&y:g[x])
{
if(y==fa[x]) continue;
dfs(y);
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,q;cin>>n>>q;
for(int i=1;i<=n;i++) cin>>c[i];
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
g[u].push_back(v),g[v].push_back(u);
}
while(q--)
{
int x,y;cin>>x>>y;
ques.push_back({x,y});
vec[x].push_back(y),vec[y].push_back(x);
}
//求lca
for(int i=1;i<=n;i++) pre[i]=i;
tarjan(1,0);
dfs(1);
for(const auto&t:ques)
{
int u=t.first,v=t.second;
int ans=0,_lca=lca[u][v];
//for(int i=1;i<=20;i++) ans=max(ans,prefix[u][i]+prefix[v][i]-prefix[_lca][i]-prefix[fa[_lca]][i]);
//这里是计算不同种类的数量，而不是计算单个种类
//prefix[u][i]+prefix[v][i]-prefix[_lca][i]-prefix[fa[_lca]][i]这里代表的是在
//u-->v的简单路径上第i种零食的数量，若小于0则代表没有！
for(int i=1;i<=20;i++)
{
if(prefix[u][i]+prefix[v][i]-prefix[_lca][i]-prefix[fa[_lca]][i]>0) ans++;
}
cout<<ans<<'\n';
}
return 0;
}综上，我们可以发现：
前缀和 vs 差分的核心区别在于：差分擅长 “批量修改区间 / 路径，最后统计结果”；前缀和擅长 “提前预处理整体信息，快速回答局部查询”。
总结：差分 vs 前缀和
| 场景 | 差分适用 | 前缀和适用 |
|---|---|---|
| 核心目标 | 批量修改多个区间 / 路径，最后统计结果 | 提前预处理整体信息，快速回答局部查询 |
| 操作方向 | 先 “分散修改”，后 “集中计算结果” | 先 “集中预处理”，后 “分散查询” |
| 典型问题 | 统计多条路径覆盖的边 / 节点次数 | 计算任意路径上的和、计数、种类等 |
| 树结构中的应用 | 树上路径批量加 / 减，最后求每个边 / 节点的累计值 | 预处理根到节点的信息，用 LCA 分解路径计算局部信息 |
okkkkkkkk了，这篇拙作花费了我大量的时间钻研，若大家觉得有用，不妨点赞+关注+收藏哟！
关注我，带你学习更多的算法知识！！！
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
5
0- 0
已为社区贡献11条内容
所有评论(0)