GESP 2025年3月六级 · P11962 · 用动画搞懂深度奇偶性
小A有一棵 n 个节点的树，节点编号 1 到 n。小A会从某个节点出发，每一步走到相邻的节点，并且只在偶数步（包括零步）后结束漫步。
题目要求：对每个节点，求出从它出发，经过偶数步能到达的节点有多少个。（可以经过重复的节点。）
1. 树：n 个节点，n-1 条边，连通无环
2. 漫步：每步移动到相邻节点，可以重复经过
3. 偶数步结束：0 步、2 步、4 步……都算偶数步
4. 对每个节点求答案：不是只求一个节点
输入一棵 3 个节点的树：1 - 3 - 2（3 是中间节点）
从节点 1 出发：0步→在1（偶数✓）；1步→到3（奇数）；2步→到1或2（偶数✓）。所以偶数步能到 {1, 2}，共 2 个。
从节点 2 出发：0步→在2（偶数✓）；1步→到3（奇数）；2步→到1或2（偶数✓）。所以偶数步能到 {1, 2}，共 2 个。
从节点 3 出发：0步→在3（偶数✓）；1步→到1或2（奇数）；2步→回到3（偶数✓）。所以偶数步能到 {3}，共 1 个。
答案：2 2 1 ✓
节点 1 和 2 的答案相同（都是 2），节点 3 的答案不同（是 1）。这和节点在树上的"位置"有关——具体来说，和节点的深度奇偶性有关！接下来我们来探索这个奥秘。
我们先在一条简单的路径上观察规律。点击"播放"，看看从节点 1 出发，走 0 步、1 步、2 步……分别能到达哪些节点。
每走一步，你移动到相邻节点。而相邻节点的"距离奇偶性"和当前节点相反——所以每走一步，奇偶性就翻转一次！
这意味着：偶数步后，你的距离奇偶性和出发时相同；奇数步后，奇偶性翻转了。
而且，你总可以在一条边上"走过去再走回来"，浪费 2 步。所以如果距离是 k，你能用 k, k+2, k+4……步到达。能偶数步到达 ⟺ 距离是偶数
现在我们把规律从"路径"推广到"树"。核心问题是：树上两个节点之间的距离，和它们的深度有什么关系？
选一个根节点（比如节点 1），深度就是从根到该节点的边数。根的深度是 0，它的孩子深度是 1，孙子深度是 2……
点击"播放"，看 BFS 如何从根节点出发，逐层计算每个节点的深度，并按奇偶性染色。
BFS 完成后，统计出偶数深度有 a 个节点，奇数深度有 b 个节点（a + b = n）。
对于每个节点 i：如果 depth[i] 是偶数，答案 = a；如果 depth[i] 是奇数，答案 = b。
就这么简单！不需要对每个节点单独搜索，只需要一次 BFS就够了。
第一步：从节点 1 出发，BFS 遍历整棵树，计算每个节点的深度。
第二步：统计偶数深度节点数 cnt[0] 和奇数深度节点数 cnt[1]。
第三步：对每个节点 i，输出 cnt[depth[i] % 2]。
1#include <bits/stdc++.h> 2using namespace std; 3 4const int MAXN = 200005; 5vector<int> adj[MAXN]; // 邻接表存树 6int depth[MAXN]; // 每个节点的深度 7int cnt[2]; // cnt[0]=偶数深度数, cnt[1]=奇数深度数 8 9void bfs(int root, int n) { 10 queue<int> q; 11 q.push(root); 12 depth[root] = 0; // 根节点深度为 0 13 bool vis[MAXN] = {}; 14 vis[root] = true; 15 16 while (!q.empty()) { 17 int u = q.front(); q.pop(); 18 cnt[depth[u] % 2]++; // 统计奇偶深度 19 20 for (int v : adj[u]) { 21 if (!vis[v]) { 22 vis[v] = true; 23 depth[v] = depth[u] + 1; // 深度 = 父节点深度 + 1 24 q.push(v); 25 } 26 } 27 } 28} 29 30int main() { 31 ios::sync_with_stdio(false); 32 cin.tie(nullptr); 33 34 int n; 35 cin >> n; 36 37 // 读入 n-1 条边，建树 38 for (int i = 0; i < n - 1; i++) { 39 int u, v; 40 cin >> u >> v; 41 adj[u].push_back(v); 42 adj[v].push_back(u); 43 } 44 45 bfs(1, n); // 从节点 1 开始 BFS 46 47 // 输出每个节点的答案 48 for (int i = 1; i <= n; i++) { 49 cout << cnt[depth[i] % 2]; 50 if (i < n) cout << ' '; 51 } 52 cout << '\n'; 53 54 return 0; 55}
第 9-28 行 bfs()：标准 BFS 模板。从根节点出发，逐层扩展。每访问一个节点，记录深度并统计奇偶。关键是 depth[v] = depth[u] + 1——BFS 天然保证先访问的深度小。
第 18 行 cnt[depth[u] % 2]++：一行代码搞定统计！depth[u] % 2 为 0 就是偶数深度，为 1 就是奇数深度。
第 49 行 cnt[depth[i] % 2]：输出答案。深度奇偶性相同 → 同一组 → 答案就是该组的人数。
时间复杂度：O(n)。BFS 每个节点和每条边只访问一次。n ≤ 2×10⁵，轻松通过。
空间复杂度：O(n)。邻接表存 n-1 条边，加上 depth 数组和队列。
如果用 O(n²) 暴力（对每个节点单独 BFS），n = 2×10⁵ 时需要 4×10¹⁰ 次运算，会超时！所以深度奇偶性这个规律非常关键。
输入：4 个节点，边为 1-3, 3-2, 4-3（节点 3 是中心）
以节点 1 为根，BFS 得到深度：depth[1]=0, depth[3]=1, depth[2]=2, depth[4]=2
偶数深度（0, 2）：节点 1, 2, 4 → cnt[0] = 3
奇数深度（1）：节点 3 → cnt[1] = 1
答案：节点 1 → 3, 节点 2 → 3, 节点 3 → 1, 节点 4 → 3
输出：3 3 1 3 ✓
自己建一棵树，看看深度奇偶性染色和每个节点的答案！
做完上面的学习，来测测你掌握了多少！共 5 道选择题。