从每个结点出发、走偶数步能到达多少个结点。
一棵 n 个结点的树。小 A 从某结点出发,每步走到相邻结点,只在偶数步(含 0 步)后结束漫步。对每个结点 i,求"从 i 出发、经过偶数步能结束漫步的结点有多少个"(中途可以重复经过结点)。
dist(s,u) 同奇偶;而绕路(来回走)只会增加偶数长度,不会改变奇偶性。树的二分图性质距离奇偶性深度统计O(n) 树遍历
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;随后 n−1 行每行 uᵢ、vᵢ |
| 输出 | n 个整数,第 i 个是结点 i 的答案 |
| 数据范围 | 1 ≤ n ≤ 2 × 10⁵ |
| 步数 | 只能是 0、2、4、6…(偶数) |
| 可否重复经过 | 可以(但不影响结论) |
dist(s,u) = dep(s) + dep(u) − 2·dep(LCA),所以奇偶性只取决于 dep(s) + dep(u)边:1–3、2–3。所以 3 是中心,1 和 2 是叶子。
以结点 1 为根:
dep(1) = 0(偶)
dep(3) = 1(奇)
dep(2) = 2(偶)
深度 = {0, 1, 2}
深度为偶:结点 1、2 → cnt[0] = 2
深度为奇:结点 3 → cnt[1] = 1
cnt = {偶:2, 奇:1}
结点 1(偶):cnt[0] = 2
结点 2(偶):cnt[0] = 2
结点 3(奇):cnt[1] = 1
✅ 输出 "2 2 1"
| 目标结点 | dist(1, ·) | 奇偶 | 偶数步可达? |
|---|---|---|---|
| 1 | 0 | 偶 | ✅(0 步,原地) |
| 2 | 2(1→3→2) | 偶 | ✅(2 步) |
| 3 | 1(1→3) | 奇 | ✗(只能 1、3、5… 步) |
结点 1 的答案是 2 ✓ 与输出一致
cnt[自身类] 至少为 1。边:1–3、3–2、4–3。这是以 3 为中心的星形(3 连着 1、2、4)。
以结点 1 为根:
dep(1) = 0(偶)
dep(3) = 1(奇)
dep(2) = 2(偶)
dep(4) = 2(偶)
cnt[偶] = 3(结点 1、2、4),cnt[奇] = 1(结点 3)
cnt = {偶:3, 奇:1}
结点 1(偶)→ 3
结点 2(偶)→ 3
结点 3(奇)→ 1
结点 4(偶)→ 3
✅ 输出 "3 3 1 3"
输出 3 3 1 3 ✓ 与样例一致
星形树很直观:从中心 3 出发,走 1 步就到某个叶子(奇数步,不允许结束),再走 1 步必须回到 3 或去别的叶子(2 步,允许)。所以从中心只能回到中心(1 个结点);而从叶子出发,2 步后可以落在任意叶子或根上(3 个结点)。这与结论完全吻合。
一次遍历求所有结点深度,按奇偶分类计数,直接得答案
ans[s] = cnt[dep(s) % 2],其中 cnt[0] 是深度为偶的结点数、cnt[1] 是深度为奇的结点数。一行就能算完,不需要任何模拟。从每个结点 BFS 若干层,标记所有偶数步可达点
| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 奇偶统计 | O(n) | ✅ 稳过 |
| 逐结点模拟 | O(n²) | ❌ 超时 |
第一行输入 n,随后 n−1 行输入每条边,程序会给出每个结点的答案。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; vector<int> g[200005]; int dep[200005]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d %d", &u, &v); g[u].push_back(v); g[v].push_back(u); } // 迭代 BFS 求深度(避免 n 大且为链时的递归爆栈) for (int i = 1; i <= n; i++) dep[i] = -1; dep[1] = 0; queue<int> q; q.push(1); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (dep[v] == -1) { dep[v] = dep[u] + 1; q.push(v); } } } // 按深度奇偶分类计数 int cnt[2] = {0, 0}; for (int i = 1; i <= n; i++) cnt[dep[i] % 2]++; // 每个结点的答案 = 与它深度同奇偶的结点个数 for (int i = 1; i <= n; i++) printf("%d%c", cnt[dep[i] % 2], i == n ? '\n' : ' '); return 0; }
dist(s,u) = dep(s) + dep(u) − 2·dep(LCA)。其中 2·dep(LCA) 必为偶数,所以 dist(s,u) 的奇偶性只由 dep(s) + dep(u) 决定——也就是"两点深度是否同奇偶"。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
dep[1] = 0 | 根的深度 | 约定根深度为 0(偶) |
queue<int> q | 迭代 BFS | 避免递归爆栈 |
cnt[dep[i] % 2]++ | 分类计数 | 按深度奇偶各统计一类 |
cnt[dep[i] % 2] | 答案 | 与自身同奇偶类的结点数 |
dep[1] = 0,导致整棵树的奇偶全反。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 2 2 1 | 题面样例 1 |
4 | 3 3 1 3 | 题面样例 2(星形) |
1 | 1 | 只有一个结点,0 步到达自己 |
2 | 1 1 | 两点距离为 1(奇),只能各自到自身 |
3 | 2 1 2 | 链 1–2–3:深度 0、1、2,cnt = {偶:2, 奇:1} |
邻接表需要存 2(n−1) 条边,加上深度数组。
✅ 约 20 万次操作,瞬间完成。本题的关键是"想到奇偶性",而不是算法本身。
// 核心结论汇总 // 树是二分图:可按"深度奇偶"把结点分成两个独立集 // 从 s 到 u 的任意路径长度 ≡ dist(s, u) (mod 2) // 走偶数步可达的结点集合 = { u : dist(s,u) 为偶数 } = 与 s 同色的结点集 // 答案[s] = cnt[dep[s] % 2] // 树上的"奇偶分层"技巧在很多题里出现 // - 判断能否用偶数步/奇数步到达 // - 树上染色(相邻结点异色) // - 树上博弈(走偶数步结束) // 求树上所有结点深度的迭代 BFS 模板 queue<int> q; dep[root] = 0; q.push(root); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) if (dep[v] == -1) { dep[v] = dep[u] + 1; q.push(v); } } // 若真的要判断"能否走恰好 k 步到达" // 由于可以来回走,只要 dist(s,u) <= k 且同奇偶即可
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 二分图性质 | 相邻异色、同色距离为偶 | 树上所有"步数奇偶"问题 |
| 深度奇偶分层 | 一次 BFS 得到两类 | 树上染色、博弈、可达性 |
| 距离公式 | dep(u)+dep(v)−2·dep(LCA) | 树上两点距离的奇偶判断 |
ans[s] = cnt[1 − dep[s] % 2]。这类"奇偶反转"的题只要改一个下标,但必须真正理解背后的二分图原理才不会写错。)