c++基础树上问题——dfs序，算法必看！
详细解释c++的dfs序加例题训练，适合参加算法比赛或对算法感兴趣的兄弟集美
·
目录
注：本文题目均来自蓝桥杯官网公开题目，仅用于算法学习和技术讨论。
一，简介：
dfs序介绍：是将树形结构转换为线性结构的一种工具，其中dfn[x]表示x在dfs过程中的顺序，
其结果是不唯一的，容易发现，对于一棵子树，其dfs序时连续的。于是dfs序可以将x的子树转化为数组上连续的一段区间[dfn[x],dfn[x]+sz[x]-1]。
重链剖分：每一条重链的dfs序也是连续的。
于是，对于子树的修改，查询等操作，可以转化为对数组的一段区间的修改和查询。
二，代码示例：
void dfs(int x, int fa)
{
dfn[x] = ++tot;
idx[dfn[x]] = x;//通过dfn找idx
sz[x] = 1;
for (const auto& y : g[x])
{
if (y == fa)continue;
dfs(y, x);
sz[x] += sz[y];
}
}三，例题详解:
例题1：蓝桥杯官网——树中颜色
问题描述
一天，小蓝在他的小屋外发现了一颗神奇的树，它的树叶上闪烁着各种不同的颜色。小蓝对这颗树产生了浓厚的兴趣，于是他决定研究这颗树的奥秘。这棵树被称为"奇幻之树"，因为它拥有神奇的能力。
每个节点都有自己独特的颜色，这些颜色代表了树上不同生物的种类。小蓝注意到，树的每个节点都有一个颜色标签 ci ，而这些颜色标签在树上不断变化，使得树上的生物多样性持续增加。
小蓝决定用算法来研究这颗树。他提出了一些问题，希望能够了解奇幻之树上不同颜色的种类数量。每次他会选择一颗树上的节点，然后探索以这个节点为根的子树中的颜色种类。
具体问题如下：给定一棵节点为 n 的有根树，根节点为 1 ，每个节点有一个颜色 ci ，小蓝有 q 组询问，每次询问给定一个节点 x ，问 x 为根的子树中，有多少种不同的颜色。
小蓝很期待你能够帮助他解决这些有趣的问题，揭示奇幻之树的神奇之处。每次你回答一个询问，都会让小蓝对这颗树的理解更进一步，同时也会使他的奇幻之旅变得更加精彩。
输入格式
第一行输入两个整数 n,q 。代表树的节点数量与询问数量。
接下来一行，输入 n 个整数 c1,c2,c3...cn， 代表每个节点的颜色。
接下来 n−1 行，每行两个整数 ui,vi，代表存在一条边连接 ui,vi 两点。
接下来 q 行， 每行一个整数 xi ，代表询问的点。
输出格式
输出 q 行，每行一个整数，代表每次询问的答案。
样例输入
5 3
1 2 3 4 5
1 2
1 3
2 4
2 5
1
2
3
样例输出
5
3
1
说明
- 1 号节点为根节点，包含 {1,2,3,4,5}共计 5 种颜色。
- 选中 2 号节点时，包含 {2,4,5} 共计 3 种颜色。
- 选中 3 号节点时，包含 {3} 共计 1 种颜色。
评测数据范围
1≤n,q≤105,1≤ci≤100,1≤ui,vi,xi≤n。
输入保证是一棵树。
代码详解：
void dfs(int x, int fa)
{
dfn[x] = ++tot;
idx[dfn[x]] = x;//通过dfn找idx
sz[x] = 1;
for (const auto& y : g[x])
{
if (y == fa)continue;
dfs(y, x);
sz[x] += sz[y];
}
}
////////////例题：树中颜色
#include <iostream>
#include<vector>
using namespace std;
const int N = 2e5 + 9;
vector<int>g[N];
int prefix[N][101];//prefix[i][col]表示在dfn为下标的数组的区间[1,i]中col节点的数量
//prefix[i][col]：表示在 DFS 序数组的区间[1,i]中颜色为col的节点数量。
int c[N];
int dfn[N], tot = 0, idx[N], sz[N];
/*dfn[N]：记录每个节点的 DFS 序编号。
tot：DFS 序计数器。
idx[N]：将 DFS 序映射回节点编号（idx[dfn[x]] = x）。
sz[N]：记录每个节点的子树大小。*/
//生成 DFS 序并计算子树大小。
void dfs(int x, int fa)//传入的是源节点的编号
{
dfn[x] = ++tot;//给每个节点编号(在dfs序中)
idx[dfn[x]] = x;//idx[dfn[x]] = x：建立时间戳到节点的反向映射。指向源节点编号
sz[x] = 1;
for (const auto& y : g[x])
{
if (y == fa)continue;
dfs(y, x);
sz[x] += sz[y];
}
}
int main()
{
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);
/*它们代表树中两个节点的编号，范围通常是1到n（题目中给定的节点总数）*/
}
dfs(1, 0);
for (int i = 1; i <= 100; i++)//i表示颜色
{
for (int j = 1; j <= n; j++)//j是dfn而不是idx
{
prefix[j][i] = prefix[j - 1][i] + (int)(c[idx[j]] == i);
}
/*对于每个颜色i，统计 DFS 序数组中前j个位置中颜色为i的节点数。
c[idx[j]]：通过 DFS 序反向查找节点的颜色。*/
/*prefix[j][i]：表示 DFS 序数组中前j个位置里，颜色为i的节点总数。
prefix[j-1][i]：前j-1个位置中颜色i的数量（前缀和的递推基础）。
c[idx[j]]：
idx[j]：将 DFS 序编号j映射回原节点编号（例如idx[3] = 5表示 DFS 序第 3 个节点是原树的节点 5）。
c[idx[j]]：查询该节点的颜色。
(int)(c[idx[j]] == i)：
如果当前节点颜色等于i，则值为 1；否则为 0。*/
}
while (q--)
{
int x; cin >> x;
int l = dfn[x], r = l + sz[x] - 1;//sz[x]=r-l+1，表示x子树大小
//l r都是的事在dfs序中的编号
int ans = 0;//记录不同颜色的数量
for (int i = 1; i <= 100; i++)
{
//检查x子树中是否存在颜色为i的节点
if (prefix[r][i] - prefix[l - 1][i] > 0)ans++;//>0说明存在该颜色
//通过前缀和数组，可在 O (1) 时间 内计算任意区间 [l, r] 中颜色 i 的出现次数：
}
cout << ans << '\n';
}
return 0;
}例题2：23年蓝桥杯真题——异或和
问题描述
给一棵含有 n 个结点的有根树，根结点为 1，编号为 i 的点有点权 ai（i∈[1,n]）。现在有两种操作，格式如下：
- 1 x y：该操作表示将点 x 的点权改为 y。
- 2 x：该操作表示查询以结点 x 为根的子树内的所有点的点权的异或和。
现有长度为 m 的操作序列，请对于每个第二类操作给出正确的结果。
输入格式
输入的第一行包含两个正整数 n,m，用一个空格分隔。
第二行包含 n 个整数 a1,a2,…,an，相邻整数之间使用一个空格分隔。
接下来 n−1行，每行包含两个正整数 ui,vi，表示结点 ui 和 vi 之间有一条边。
接下来 m 行，每行包含一个操作。
输出格式
输出若干行，每行对应一个查询操作的答案。
样例输入
4 4
1 2 3 4
1 2
1 3
2 4
2 1
1 1 0
2 1
2 2
样例输出
4
5
6
评测用例规模与约定
对于 30% 的评测用例，n,m≤1000；
对于所有评测用例，1≤n,m≤100000，0≤ai,y≤100000，1≤ui,vi,x≤n。
这道题和上一道相比就难很多了，还运用到了树状数组，位运算等知识点，对选手能力考察较高
方法1：树状数组法
//题目中1 x y的x指的是编号，而不是权值！
#include <iostream>
#include<vector>
using namespace std;
const int N = 2e5 + 9;
vector<int>g[N];
int a[N], t[N], n;//t[] 是树状数组（Fenwick Tree）的核心数组，
//它并不直接存储原始点权，而是以一种分层前缀和的方式维护异或值。
//t[i] 存储的是区间 [i - lowbit(i) + 1, i] 的DFS 序中对应位置的点权权值的异或和
int c[N];
int dfn[N], tot = 0, idx[N], sz[N];
int lowbit(int x)//用于快速计算一个整数在二进制表示下最低位的 1 所对应的值
{
return x & -x;
}
/*x = 6 → 二进制: 0000 0110
~x → 二进制: 1111 1001
~x + 1 = -x → 二进制: 1111 1010
x & (-x) → 二进制: 0000 0010 → 十进制: 2*/
//lowbit(x) 的值等于 2^k，其中 k 是 x 的二进制末尾连续 0 的个数
void update(int k, int x)//将dfs序中位置 k 的点权值异或 x
{//k：DFS 序中的位置（对应节点的 dfn 值）。
for (int i = k; i <= n; i += lowbit(i))t[i] ^= x;
//树状数组 t[] 的每个位置 i 维护的是一个区间的异或和，区间长度为 lowbit(i)
//t[i] 存储的是区间 [i - lowbit(i) + 1, i] 的异或和
//从 i 开始，每次加上 lowbit(i)，直到超过数组长度。
}
/*对于使用t[]:当更新单点 i 时，需要修改所有包含 i 的区间。
由于每个数 i 最多可以分解为 O(log n) 个 2 的幂次，因此只需更新 O(log n) 个区间，
若用普通数组则是o(n)*/
/*1. 树状数组t[的核心思想：二进制分层
树状数组的设计基于二进制分解：每个整数 i 都可以分解为多个 2 的幂次之和。例如：
7 = 4 + 2 + 1（二进制 111）
6 = 4 + 2（二进制 110）
树状数组将数组分成多个区间，每个区间的长度为 2 的幂次，且区间的右端点为 i。具体来说：
t[i] 负责的区间长度为 lowbit(i)，即 i 的二进制最低位 1 对应的值。
区间左端点为 i - lowbit(i) + 1，右端点为 i。*/
/*3. 数学性质：异或的区间可加性
异或运算满足区间可加性：对于区间 [a, c]，有：
XOR[a, c] = XOR[a, b] ^ XOR[b+1, c]
因此，前缀异或和 XOR[1, k] 可以通过树状数组快速合并多个不重叠子区间的异或和。*/
/*t[5] 覆盖 [5, 5]
t[6] 覆盖 [5, 6]（因为 6 - lowbit(6) + 1 = 5）
t[8] 覆盖 [1, 8]（包含位置 5）
当更新单点 5 时，所有包含 5 的区间都需要被修改，以保证后续查询的正确性。
示例演示
假设初始时 t[] 全为 0，执行 update(5, 3) 后：
t[5] ^= 3：
t[5] 原本为 0，更新后为 0 ^ 3 = 3。
t[6] ^= 3：
t[6] 原本为 0，更新后为 0 ^ 3 = 3。
t[8] ^= 3：
t[8] 原本为 0，更新后为 0 ^ 3 = 3。
此时：
t[5] = 3（表示区间 [5, 5] 的异或和为 3）
t[6] = 3（表示区间 [5, 6] 的异或和为 3，但实际上 6 位置的值未被修改，这只是中间状态）
t[8] = 3（表示区间 [1, 8] 的异或和为 3，同样是中间状态）*/
/*update(5, 3) 的作用是：将 DFS 序中位置 5 的点权异或上 3，
并递归更新所有包含该位置的区间节点，确保后续查询能正确反映修改后的值。这种更新方式通过 O(log n) 的时间复杂度，
维护了区间异或和的正确性。*/
int query(int k)//用于高效计算前 k 个元素的异或和。
{
int res = 0;
for (int i = k; i > 0; i -= lowbit(i))res ^= t[i];
return res;
}//query 函数计算的是点权的异或和
/*查询前缀和 query(k) 时，需要合并所有右端点 ≤ k 的区间。
通过二进制分解，任何数 k 都可以表示为 O(log n) 个区间的并集：
实现高效查询
示例：查询 query(7) 时，分解为区间 7 → 6 → 4，共 O(log n) 个节点。*/
void dfs(int x, int fa)//传入的是源节点的编号
{
dfn[x] = ++tot;//给每个节点编号(在dfs序中)
idx[dfn[x]] = x;//idx[dfn[x]] = x：建立时间戳到节点的反向映射。指向源节点编号
sz[x] = 1;
for (const auto& y : g[x])
{
if (y == fa)continue;
dfs(y, x);
sz[x] += sz[y];
}
}
int main()
{
int q; cin >> n >> q;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i < n; i++)
{
int u, v; cin >> u >> v;
g[u].push_back(v), g[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++)update(dfn[i], a[i]);
while (q--)
{
int op; cin >> op;
if (op == 1)//更新x为y
{
int x, y; cin >> x >> y;
int val = query(dfn[x]) ^ query(dfn[x] - 1);
//在初始状态（未进行任何更新操作时），query(dfn[x]) ^ query(dfn[x] - 1) 等于 a[x]；
// 但在经过更新操作后，它等于节点 x 当前的最新值（而非初始的 a[x]）！！！！！！
//val 表示的是 DFS 序中某一点的当前点权值
/*query(dfn[x]) 返回区间 [1, dfn[x]] 的异或和。
query(dfn[x]-1) 返回区间 [1, dfn[x]-1] 的异或和。
两者异或后，得到的 val 就是位置 dfn[x] 对应的点权（即节点 x 的当前值）。*/
update(dfn[x], val ^ y);//这一步的意思就是将dfn[x]所代表的点权（就是val）在和val^y进行异或运算
//val^vla^y=0^y=y，至此，val被替换成y！！！
}
else//求异或和
{
int x; cin >> x;
int l = dfn[x], r = dfn[x] + sz[x] - 1;
int ans = query(r) ^ query(l - 1);//类似prefix
//ans表示l到r的异或和
/*异或（XOR，符号为 ^）具有以下关键性质：
交换律：a ^ b = b ^ a
结合律：(a ^ b) ^ c = a ^ (b ^ c)
自反性：a ^ a = 0（任何数异或自身为 0）
单位元：a ^ 0 = a（任何数异或 0 等于自身）*/
//定义 prefix[i] 为前 i 个元素的异或和：
//prefix[i] = a[1] ^ a[2] ^ ... ^ a[i]
//则区间 [l, r] 的异或和可表示为：
//a[l] ^ a[l+1] ^ ... ^ a[r] = prefix[r] ^ prefix[l-1]
//前面的1到l-1部分由交换律a[i]^a[i]=0,都抵消了
cout << ans << '\n';
}
}
return 0;
}方法2：更简单直观的方法
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int>edge[N];//edge[i]存储第i个结点的邻接点
int in_[N], out[N];//in_[i]存储第i个结点的入序,out[i]存储第i个结点的出序
int weight[N];//weight[i]存储的第i个结点的值(原始数据)
int tot = 0;//记录dfs序的变量
int seq[N];//seq[i]为dfs序中第i个结点的权值
int n, m;
void dfs(int u, int father)//对结点u进行dfs,其父结点为father
{
in_[u] = ++tot;//进入函数,计算入序,tot先自加
seq[tot] = weight[u];//第tot个结点的权值是weight[u]
for (const auto& v : edge[u])//遍历u的邻接点v
{
if (v == father)continue;
dfs(v, u);
}
out[u] = tot;//退出函数,更新u的出序,tot无需自加
}
/*in_[u]：表示节点u在 DFS 遍历中首次被访问的时间戳（即进入节点u的时间）。
这个时间戳是唯一的，并且在整个 DFS 过程中严格递增。
out[u]：表示节点u的所有子树都被遍历完成后，退出节点u的时间戳。
由于 DFS 会递归遍历当前节点的所有子节点，
因此out[u]实际上等于当前节点及其所有子树的节点总数（从in_[u]开始的连续区间）。*/
/*入序（in_）：在递归进入节点u时立即记录，确保每个节点的入序唯一且递增。
出序（out）：在遍历完所有子节点后记录，此时的tot值恰好等于当前子树的最后一个节点的入序，
因此out[u]表示子树区间的右端点。*/
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)scanf("%d", &weight[i]);//输入n个结点的原始值
for (int i = 1; i < n; i++)//输入n-1条无向边
{
int u, v; scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1, 0);//从1号结点开始进行一次dfs,求出所有结点的dfs序,填写in_数组和out数组
//此后我们只按照dfs序处理结点,原始的weight不再使用
while (m--)
{
int op, x, y;
scanf("%d", &op);
if (op == 1)//把第x个结点的权值改为y
{
scanf("%d%d", &x, &y);
seq[in_[x]] = y;//转化为将第in_[x]个结点(dfs序下)的权值改为y
}
else if (op == 2)
{
scanf("%d", &x);//查询以x为根的子树的异或和
int ans = 0;
for (int i = in_[x]; i <= out[x]; i++)//转化为求区间[ in_[x],out[x] ]的异或和
{
ans = ans ^ seq[i];
}
printf("%d\n", ans);
//注意这里使用的是暴力求前缀和的方式而不是前缀和数组
//这是因为本题是一边修改一边查询,前缀和数组无法实现动态修改和查询
//如果要提高效率可以使用线段树,可在O(logn)时间复杂度内完成查询
//但对于本题,暴力求异或和即可通过全部测试点
}
}
return 0;
}okkkk了，大家觉得不错的话，记得点赞+关注+收藏哟！
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
10
0- 0
已为社区贡献11条内容
所有评论(0)