GESP 题解库 / 6 级题解 / [GESP202503 六级] 树上漫步 · 第 10 / 27 题
GESP202503 六级 · P11962 · 简单

树上漫步

从每个结点出发、走偶数步能到达多少个结点。

📊
n ≤ 2 × 10⁵
结点数量
🔢
int
数值类型
⚡
O(n)
时间复杂度
🎯
树的二分图性质
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

一棵 n 个结点的树。小 A 从某结点出发,每步走到相邻结点,只在偶数步(含 0 步)后结束漫步。对每个结点 i,求"从 i 出发、经过偶数步能结束漫步的结点有多少个"(中途可以重复经过结点)。

💡
人话翻译:关键结论一句话——从 s 出发走偶数步能到 u,当且仅当 s 与 u 的距离为偶数。
原因是树是二分图:任何一条从 s 到 u 的路径长度都与 dist(s,u) 同奇偶;而绕路(来回走)只会增加偶数长度,不会改变奇偶性。
于是只需统计每个结点到根的距离奇偶,用两类计数数组就能 O(1) 回答每个结点。

🔍 关键词提取

树的二分图性质距离奇偶性深度统计O(n) 树遍历

已知条件

项目说明
输入第一行 n;随后 n−1 行每行 uᵢ、vᵢ
输出n 个整数,第 i 个是结点 i 的答案
数据范围1 ≤ n ≤ 2 × 10⁵
步数只能是 0、2、4、6…(偶数)
可否重复经过可以(但不影响结论)

需要解决的问题

02
思维导图
整理解题思路的全貌
🌳 偶数步可达 ⟺ 距离为偶数
🧠 核心结论
树是二分图
任意路径长度与 dist 同奇偶
走回头路只增加偶数长度
所以偶数步可达 = 距离为偶数
📊 统计方法
求每个结点到根的深度 dep
按 dep 的奇偶分两类
cnt[0] = 深度为偶的个数
cnt[1] = 深度为奇的个数
✅ 答案
dist(s,u) 偶 ⟺ dep(s)、dep(u) 同奇偶
所以答案 = dep(s) 所在类的个数
每个结点 O(1)
输出 n 个数
⚠️ 易错点
用 DFS 递归(n 大可爆栈)
以为要真的模拟走偶数步
把"可达的步数"和"可达的结点"混淆
根结点深度算错(应为 0)
03
样例手算推导
两个样例的推演

🧮 样例 1:3 个结点的"V"形树

边:1–3、2–3。所以 3 是中心,1 和 2 是叶子。

1
任选一个结点当根,求深度

以结点 1 为根:

dep(1) = 0(偶)

dep(3) = 1(奇)

dep(2) = 2(偶)

深度 = {0, 1, 2}

2
按奇偶分类计数

深度为偶:结点 1、2 → cnt[0] = 2

深度为奇:结点 3 → cnt[1] = 1

cnt = {偶:2, 奇:1}

3
逐个求答案

结点 1(偶):cnt[0] = 2

结点 2(偶):cnt[0] = 2

结点 3(奇):cnt[1] = 1

✅ 输出 "2 2 1"

📊 手工验证结点 1

目标结点dist(1, ·)奇偶偶数步可达?
10偶✅(0 步,原地)
22(1→3→2)偶✅(2 步)
31(1→3)奇✗(只能 1、3、5… 步)

结点 1 的答案是 2 ✓ 与输出一致

🔑
注意"0 步"也算:题目说"只在偶数步(可以是零步)后结束漫步",所以出发结点自己也算一个可达结点。这解释了为什么答案里总有 cnt[自身类] 至少为 1。

🧮 样例 2:4 个结点的星形树

边:1–3、3–2、4–3。这是以 3 为中心的星形(3 连着 1、2、4)。

1
深度与分类

以结点 1 为根:

dep(1) = 0(偶)

dep(3) = 1(奇)

dep(2) = 2(偶)

dep(4) = 2(偶)

cnt[偶] = 3(结点 1、2、4),cnt[奇] = 1(结点 3)

cnt = {偶:3, 奇:1}

2
逐个求答案

结点 1(偶)→ 3

结点 2(偶)→ 3

结点 3(奇)→ 1

结点 4(偶)→ 3

✅ 输出 "3 3 1 3"

输出 3 3 1 3 ✓ 与样例一致

💡 直观理解

星形树很直观:从中心 3 出发,走 1 步就到某个叶子(奇数步,不允许结束),再走 1 步必须回到 3 或去别的叶子(2 步,允许)。所以从中心只能回到中心(1 个结点);而从叶子出发,2 步后可以落在任意叶子或根上(3 个结点)。这与结论完全吻合。

⚠️
不要试图"模拟走偶数步":步数没有上限,逐层 BFS 会超时。本题的解法是"一步到位"的数学结论,这也是它作为 6 级题的核心考点——识别出"奇偶性"这个不变量。
04
解法对比
奇偶统计 O(n) vs 模拟 BFS

⚔️ 解法对比

🟢 深度奇偶统计(推荐) 推荐

一次遍历求所有结点深度,按奇偶分类计数,直接得答案

  • 时间 O(n)
  • n = 2 × 10⁵ 时约 2 × 10⁵
  • 代码 20 行
  • 空间 O(n)
💡
答案公式:ans[s] = cnt[dep(s) % 2],其中 cnt[0] 是深度为偶的结点数、cnt[1] 是深度为奇的结点数。一行就能算完,不需要任何模拟。

🟠 模拟"走 0、2、4、… 步"

从每个结点 BFS 若干层,标记所有偶数步可达点

  • 步数无上限
  • 从每个结点做 BFS:O(n²)
  • n = 2 × 10⁵ 时 4 × 10¹⁰
  • 必然超时
⚠️
为什么不能用模拟:因为"偶数步"没有上限,要枚举到多少步才停?而实际上可达集合很快就"稳定"了——这个"稳定"正对应"距离奇偶性"这个不变量。

📈 性能对比

方案复杂度可行性
奇偶统计O(n)✅ 稳过
逐结点模拟O(n²)❌ 超时
05
算法流程图
一次遍历求深度并按奇偶计数
开始读入 n,用邻接表建树以结点 1 为根,用栈做迭代 BFS/DFS,求每个结点的深度 dep统计 cnt[0] = 深度为偶的结点数,cnt[1] = 深度为奇的结点数i 从 1 到 nans[i] = cnt[dep[i] 的奇偶]输出 ans[1..n]i 加 1 处理下一个结点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌳 偶数步可达结点数

第一行输入 n,随后 n−1 行输入每条边,程序会给出每个结点的答案。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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;
}
🔑
为什么答案是"深度同奇偶的结点数"?对树上任意两点 s、u,距离公式是dist(s,u) = dep(s) + dep(u) − 2·dep(LCA)。其中 2·dep(LCA) 必为偶数,所以 dist(s,u) 的奇偶性只由 dep(s) + dep(u) 决定——也就是"两点深度是否同奇偶"。
注意这里的"根"可以任选(我们选了结点 1),因为奇偶性的结论与根的选取无关。

📖 关键几行怎么看

代码作用为什么这样写
dep[1] = 0根的深度约定根深度为 0(偶)
queue<int> q迭代 BFS避免递归爆栈
cnt[dep[i] % 2]++分类计数按深度奇偶各统计一类
cnt[dep[i] % 2]答案与自身同奇偶类的结点数
⚠️
四个坑:① 用递归 DFS(n = 2 × 10⁵ 且为链时爆栈);② 以为要真的模拟走偶数步;③ 把答案理解成"经过偶数步的步数"(题目问的是结点个数);④ 忘记 dep[1] = 0,导致整棵树的奇偶全反。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
1 3 / 2 3
2 2 1题面样例 1
4
1 3 / 3 2 / 4 3
3 3 1 3题面样例 2(星形)
11只有一个结点,0 步到达自己
2
1 2
1 1两点距离为 1(奇),只能各自到自身
3
1 2 / 2 3
2 1 2链 1–2–3:深度 0、1、2,cnt = {偶:2, 奇:1}
✅
自查清单:① 用 BFS 求深度吗?② 按深度奇偶分类了吗?③ 答案取同类计数吗?

🚨 易错点清单

⚠️
递归 DFS:n = 2 × 10⁵ 的链状数据会爆栈,应用 BFS 或迭代栈。
⚠️
真的模拟走偶数步:步数无上限,应该用"距离奇偶性"这个结论。
⚠️
答案含义理解错:问的是"可达的结点个数",不是步数。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
n 最大
2 × 10⁵
运算量
约 2 × 10⁵

时间怎么算的?

空间都用在哪?

邻接表需要存 2(n−1) 条边,加上深度数组。

✅ 约 20 万次操作,瞬间完成。本题的关键是"想到奇偶性",而不是算法本身。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 核心结论汇总
// 树是二分图:可按"深度奇偶"把结点分成两个独立集
// 从 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]。这类"奇偶反转"的题只要改一个下标,但必须真正理解背后的二分图原理才不会写错。)