欢迎大家订阅我的CSDN专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：[P11962 GESP202503 六级] 树上漫步 - 洛谷
【题目描述】
小 A 有一棵 \(n\) 个结点的树，这些结点依次以 \(1,2,⋯,n\) 标号。
小 A 想在这棵树上漫步。具体来说，小 A 会从树上的某个结点出发，每⼀步可以移动到与当前结点相邻的结点，并且小 A 只会在偶数步（可以是零步）后结束漫步。
现在小 A 想知道，对于树上的每个结点，从这个结点出发开始漫步，经过偶数步能结束漫步的结点有多少个（可以经过重复的节点）。
【输入】
第一行，一个正整数 \(n\)。
接下来 \(n−1\) 行，每行两个整数 \(u_i,v_i\)，表示树上有⼀条连接结点 \(u_i\) 和结点 \(v_i\) 的边。
【输出】
一行，\(n\) 个整数。第 \(i\) 个整数表示从结点 \(i\) 出发开始漫步，能结束漫步的结点数量。
【输入样例】
3
1 3
2 3
【输出样例】
2 2 1
【算法标签】
《洛谷 P11962 书上漫步》 #二分图# #树的遍历# #GESP# #2025#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 5; // 定义最大节点数
int n, cnt; // n: 节点数，cnt: 记录被标记的节点数
int h[N], e[N * 2], ne[N * 2], idx; // 邻接表存储树结构
bool vis[N], a[N]; // vis: 记录节点是否访问过，a: 记录节点是否被标记// 添加边到邻接表
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}// 深度优先搜索
void dfs(int u, int step) {if (vis[u]) return; // 如果节点已访问，直接返回// 如果当前步数为偶数，标记该节点并增加计数if (step % 2 == 0) {a[u] = 1;cnt++;}vis[u] = 1; // 标记节点为已访问// 遍历当前节点的所有邻居for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];dfs(j, step + 1); // 递归访问邻居，步数加1}
}int main() {cin >> n; // 输入节点数memset(h, -1, sizeof h); // 初始化邻接表// 构建树的邻接表for (int i = 1; i < n; i++) {int x, y;cin >> x >> y; // 输入边add(x, y), add(y, x); // 无向图，添加双向边}dfs(1, 0); // 从节点1开始DFS，初始步数为0// 输出结果for (int i = 1; i <= n; i++) {if (a[i]) cout << cnt << " "; // 如果节点被标记，输出标记节点数else cout << n - cnt << " "; // 否则输出未标记节点数}cout << endl;return 0;
}
【运行结果】
3
1 3
2 3
2 2 1