GESP 题解库 / 7 级题解 / [GESP202409 七级] 小杨寻宝 · 第 13 / 24 题
GESP202409 七级 · P11249 · 中等

小杨寻宝

每条边至多走一次 ⟺ 走的必然是一条简单路径;问题化为"所有宝物是否落在同一条路径上"。

🌳
n ≤ 10⁵
树的节点数
🔁
t ≤ 10
数据组数
⚡
O(n)
每组时间复杂度
🎯
子树宝物计数
核心判据
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨有一棵包含 n 个节点的树,树上的一些节点放置有宝物。

小杨可以任意选择一个节点作为起点并在树上移动,但是他只能经过每条边至多一次,当小杨经过一条边后,这条边就会消失。小杨每经过一个放置有宝物的节点就会取得该宝物。

请判断小杨能否成功取得所有宝物。本题单个测试点内有多组测试数据:第一行 t,随后每组给出 n、长度为 n 的 0/1 序列 a(aᵢ = 1 表示节点 i 有宝物)以及 n − 1 条边。能取完输出 Yes,否则输出 No。

💡
人话翻译:每条边只能用一次,这件事等价于"走过的路不会绕圈"——一旦绕圈,中间那个点就被经过了两次。
所以小杨的整段行走,本质上就是树上的一条简单路径:从某个点出发,一路不回头地走到另一个点。
于是问题变成:能不能找到一条路径,把所有宝物节点都串起来?换句话说——所有宝物是否落在同一条路径上。

🔍 关键词提取

树上路径每条边至多一次子树宝物计数分支数判据

已知条件

项目说明
输入t 组;每组先给 n,再给 n 个 0/1,最后 n − 1 条边
输出每组一行 Yes 或 No
数据范围1 ≤ t ≤ 10,1 ≤ n ≤ 10⁵,aᵢ ∈ {0, 1}
保证树上至少有一个宝物(不必担心全是 0)
起点任意选择;只需判断可行性,不用输出路径

需要解决的问题

02
思维导图
整理解题思路的全貌
🌳 每条边至多走一次 ⟺ 一条简单路径
🧠 关键转化
每条边至多一次 → 不能绕圈
走过的点必然两两不同
整段行走 = 一条简单路径
问题 = 宝物能否被一条路径串起
📐 判定思路
以 1 号点为根做一次迭代 DFS
cnt[v] = 子树内宝物个数
tot = 宝物总数
数每个节点的"含宝物方向数"
⚠️ 写代码的坑
n = 10⁵ 递归会爆栈 → 改用迭代
t 组数据要清空图与标记数组
根节点没有"父方向"
tot = 1 时答案恒为 Yes
03
样例手算推导
两组样例的完整推演

🧮 样例 1 第 1 组:a = 0 1 0 1 0,边 1-2、1-3、3-4、3-5,答案 Yes

宝物在节点 2 和节点 4,共 2 个。以 1 号点为根,先算每个节点的子树宝物数 cnt。

1
第一步:求 cnt(子树内的宝物个数)

叶子 4 有宝物 → cnt[4] = 1

叶子 5 无宝物 → cnt[5] = 0

节点 3 = a₃ + cnt[4] + cnt[5] = 0 + 1 + 0 = 1

节点 2 = a₂ = 1

节点 1 = a₁ + cnt[2] + cnt[3] = 0 + 1 + 1 = 2 = tot ✓

✅ tot = 2

2
第二步:数每个节点的"含宝物的方向数"

方向 = 一个儿子子树(cnt > 0)+ 父节点一侧(tot − cnt[u] > 0)

节点 1:儿子 2、3 都含宝物 → 2 个方向;父方向 tot − cnt[1] = 0 → 不算

节点 2:没有儿子 → 0;父方向 2 − 1 = 1 > 0 → 1 个

节点 3:儿子 4 含宝物、儿子 5 不含 → 1;父方向 2 − 1 = 1 > 0 → 共 2 个

节点 4:父方向 2 − 1 = 1 > 0 → 1 个;节点 5:父方向 2 > 0 → 1 个

最大值 2,没有达到 3

✅ 最大方向数 = 2 < 3 → Yes

节点cnt[v]儿子中含宝物的方向数父方向有宝物?方向总数
12儿子 2、3(2 个)2 − 2 = 0 → 否2
21无儿子2 − 1 = 1 → 是1
31儿子 4(1 个,5 不含)2 − 1 = 1 → 是2
41无儿子2 − 1 = 1 → 是1
50无儿子2 − 0 = 2 → 是1
🔑
这条路径长什么样?样例解释给出的是 2 − 1 − 3 − 4:正好把宝物 2、4 串在一条线里。注意宝物数目 tot = 2 时,任意两个点之间都有一条路径,所以 tot ≤ 2 的情况答案一定是 Yes。

🧮 样例 1 第 2 组:a = 1 1 1 1 1,同样的树,答案 No

这次 5 个节点全都是宝物,tot = 5。

1
第一步:求 cnt

cnt[4] = 1,cnt[5] = 1

cnt[3] = a₃ + cnt[4] + cnt[5] = 1 + 1 + 1 = 3

cnt[2] = 1

cnt[1] = 1 + 1 + 3 = 5 = tot ✓

✅ tot = 5

2
第二步:节点 3 出事

节点 3 的儿子 4、5 都含宝物 → 2 个方向

父方向 tot − cnt[3] = 5 − 3 = 2 > 0 → 再加 1 个

方向总数 = 2 + 1 = 3 ≥ 3

这意味着宝物分散在 3 条互不重合的方向上

❌ 3 ≥ 3 → No

📊 为什么 3 个方向就一定不行?

经过节点 3 的路径能覆盖的方向漏掉的宝物
4 − 3 − 5儿子 4、儿子 5 两个方向节点 1、2(父方向)
4 − 3 − 1(−2)儿子 4 + 父方向节点 5
5 − 3 − 1(−2)儿子 5 + 父方向节点 4
不经过节点 3 的路径至多落在一个方向内另外两个方向全漏
⚠️
直觉上最容易错的一点:很多人以为"边走边捡,走不动了换个起点再走"就能捡完,但本题只能选一次起点、走一条连续的路。
路径经过一个点时,只能"顺路"连到它相邻的两个方向,第三个方向必然要额外拐一次——那就得重复走边了。
所以"存在节点的含宝物方向数 ≥ 3"是 No 的充要条件。
04
解法对比
子树计数 vs 求"宝物点集直径"两次 BFS

⚔️ 解法对比

🟢 子树计数(推荐) 推荐

以 1 为根一次 DFS 求出 cnt,检查每个节点的含宝物方向数是否 ≥ 3

  • 时间 O(n),只扫两遍
  • 不需要 LCA、不需要倍增表
  • 代码约 35 行
  • 判据直接对应"能不能用一条路径装下"
💡
判据为什么充要?若所有宝物落在某条路径 P 上,则对任意节点 u,含宝物的方向最多只有 2 个(P 在 u 处最多占用两个方向)→ 不会触发 No。
反过来若所有节点方向数都 ≤ 2,从"最外侧"的两个宝物出发的路径就能覆盖全部宝物 → Yes。

🟠 两次 BFS 求宝物点集直径

任取宝物 s,BFS 找最远宝物 a;再从 a BFS 找最远宝物 b,最后验证每个宝物都在 a↔b 上

  • 时间也是 O(n)
  • 但要做 2 次 BFS + 1 次检查
  • 代码约 60 行
  • 几何意义清晰:所有点共线 ⟺ 都在直径上
⚠️
校验"点在路径上"的公式:dist(a, x) + dist(x, b) == dist(a, b)。
两次 BFS 已经把 dist(a, ·) 和 dist(b, ·) 都算出来了,所以检查是 O(1) 一个点。思路更"几何",但代码更长、常数更大。

📈 性能对比

方案复杂度代码量
子树计数 + 方向判据O(n)约 35 行
两次 BFS 求点集直径O(n)约 60 行
枚举路径 / 模拟所有行走指数级❌ 不可行
05
算法流程图
一次 DFS 定父亲 → 逆序累加子树 → 数方向
开始:读入 n、a[] 和 n − 1 条边以 1 号点为根,用迭代 DFS 求 par[] 与遍历序 order[]把 cnt[] 初始化为 a[],再逆序执行 cnt[par[u]] += cnt[u]tot = 所有 a_i 之和(宝物总数)对每个节点 u,统计含宝物的方向数(含宝物的儿子个数 + 父方向)存在某个节点的方向数 ≥ 3 吗?是 → No宝物分散在 3 条以上分支,一条路径装不下否 → Yes所有宝物都落在同一条路径上输出 Yes / No
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌳 小杨寻宝判定器

按题目格式输入一棵小树(第一行 n,第二行 n 个 0/1,之后 n−1 行每行一条边),程序会用"子树宝物计数 + 方向数判据"给出 Yes / No,并列出每个节点的 cnt 与方向数。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码(迭代 DFS + 子树宝物计数)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int n, a[MAXN], cnt[MAXN], par[MAXN];
bool vis[MAXN];
vector<int> g[MAXN];

bool solve() {
    scanf("%d", &n);
    int tot = 0;
    for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); tot += a[i]; }
    for (int i = 1; i <= n; i++) g[i].clear();     // 多组数据:清空邻接表

    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }

    // 迭代 DFS(n 可达 1e5,递归会爆栈)
    for (int i = 1; i <= n; i++) { vis[i] = false; par[i] = 0; cnt[i] = a[i]; }
    vector<int> order;
    order.reserve(n);
    stack<int> st;
    st.push(1); vis[1] = true;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        order.push_back(u);
        for (int v : g[u]) {
            if (!vis[v]) { vis[v] = true; par[v] = u; st.push(v); }
        }
    }

    // 逆序遍历:把儿子的 cnt 累加给父亲
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        if (par[u]) cnt[par[u]] += cnt[u];
    }

    // 检查每个节点"含宝物的方向数"是否 >= 3
    for (int u = 1; u <= n; u++) {
        int br = 0;
        for (int v : g[u]) if (par[v] == u && cnt[v] > 0) br++;   // 儿子方向
        if (tot - cnt[u] > 0) br++;                               // 父方向
        if (br >= 3) return false;
    }
    return true;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) printf("%s\n", solve() ? "Yes" : "No");
    return 0;
}
🔑
为什么"含宝物方向数 ≥ 3"就一定是 No?把小杨的行走看成一条路径 P。若 P 经过 u,那么 P 在 u 处最多"占用"两个方向(沿着路径进来、再沿着另一个方向出去)。
若 u 有 3 个方向都含宝物,则至少有一个方向的宝物既不在 P 的进入侧、也不在出去侧,要拿到它就必须从 u 再拐一次,于是某条边被走了两遍 → 不可能。
反之若所有节点方向数都 ≤ 2,从"最外侧"的两个宝物出发的那条路径正好覆盖全部宝物。

📖 关键几行怎么看

代码作用为什么这样写
cnt[i] = a[i]初始化子树和先把自身宝物算进去,后面的子树和才完整
for (i = order.size()−1; i >= 0; i--)逆序累加逆序遍历保证先算儿子再算父亲
if (par[u]) cnt[par[u]] += cnt[u];往上汇总根节点的 par = 0,不会越界,也不会被累加
if (tot − cnt[u] > 0) br++;父方向tot − cnt[u] 就是"子树外"的宝物数
g[i].clear()多组清空t 组数据共用全局数组,不清空会串数据
⚠️
四个坑:① 用递归 DFS 在 n = 10⁵(链状树)时爆栈 → 必须迭代;② 忘记清空邻接表(g[i].clear())导致跨组污染;③ 把"方向数 ≥ 3"写成"度数 ≥ 3"——度数 3 但只有一个方向含宝物是完全合法的;④ 求 cnt 时用正序遍历(父亲还没拿到儿子的值)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
2
5
0 1 0 1 0
1 2
1 3
3 4
3 5
5
1 1 1 1 1
1 2
1 3
3 4
3 5
Yes
No
题面样例(两组)
1
1
1
Yes只有一个节点、只有一个宝物
1
3
0 1 1
1 2
1 3
Yes两个宝物分居中心两侧,方向数恰好 2
1
4
0 1 1 1
1 2
1 3
1 4
No菊花:中心有 3 个含宝物方向
1
2
1 1
1 2
Yesn = 2 的最小 Yes
1
5
1 0 0 0 1
1 2
2 3
3 4
4 5
Yes链的两端是宝物,中间无宝物
1
5
1 0 1 0 1
1 2
2 3
3 4
4 5
Yes链上隔位放宝物
1
6
1 1 0 1 1 0
1 2
1 3
3 4
3 5
5 6
No宝物分布在两个分支上
1
6
1 1 0 1 0 0
1 2
1 3
3 4
3 5
5 6
Yes分支上恰好没有宝物
1
2
0 1
1 2
Yestot = 1 恒为 Yes
✅
自查清单:① 迭代 DFS 吗?② 逆序累加 cnt 吗?③ 父方向用 tot − cnt[u] 判吗?④ 每组都清空图了吗?

🚨 易错点清单

⚠️
递归 DFS:n = 10⁵ 且树退化成链时递归深度 10⁵,直接爆栈,必须用栈迭代。
⚠️
判据写错:判定的是"含宝物的方向数 ≥ 3",不是节点的度数 ≥ 3。
⚠️
多组数据不清空:t 组共用 g[]、cnt[]、vis[],漏清空会串数据。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

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

时间怎么算的?

空间都用在哪?

邻接表存 2(n − 1) 条无向边(约 2 × 10⁵ 个 int),再加 cnt / par / vis / order 四个长度 n 的数组。

✅ 每组线性,t ≤ 10 时总运算量约 3 × 10⁶,1 s 内轻松通过,而且完全不依赖 n 的形态(链、菊花、随机树都一样快)。

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

🔗 常用技巧小抄

// 1) 核心转化:每条边至多走一次 ⇒ 走过的点两两不同 ⇒ 一条简单路径
//    若重复经过点 u,两次经过之间是闭合回路,回路上的边被走了两次 ❌

// 2) 判"所有宝物能否被一条路径装下":数每个节点的含宝物方向数
int br = 0;
for (int v : g[u]) if (par[v] == u && cnt[v] > 0) br++;  // 每个含宝物的儿子 = 1 个方向
if (tot - cnt[u] > 0) br++;                              // 子树外还有宝物 = 父方向
if (br >= 3) return false;                               // 3 个方向装不下

// 3) 迭代 DFS 求"父亲 + 逆序子树和"(n = 1e5 别用递归)
stack<int> st; st.push(1); vis[1] = true;
while (!st.empty()) {
    int u = st.top(); st.pop(); order.push_back(u);
    for (int v : g[u]) if (!vis[v]) { vis[v] = true; par[v] = u; st.push(v); }
}
for (int i = order.size() - 1; i >= 0; i--) {
    int u = order[i];
    if (par[u]) cnt[par[u]] += cnt[u];
}

// 4) 多组数据的清空:邻接表、vis、par、cnt 一个都不能漏
for (int i = 1; i <= n; i++) g[i].clear();

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
树上子树计数cnt[v] = 子树内宝物个数子树和、树上连通块大小、树形 DP 转移
"方向数 ≥ 3"判据判断点集能否被一条路径覆盖树的直径、点覆盖问题、路径覆盖最小条数
迭代 DFSn = 10⁵ 时不爆栈所有深树遍历、拓扑排序、强连通分量
多组数据清空t ≤ 10 组共用全局数组一切多测题目(尤其是清空 vector)
🌟
思考题:如果题目改成"每条边至多走两次",答案会变成什么?(提示:就永远都是 Yes 了。因为此时允许"回头路",从任意节点出发做一次完整的 DFS 并沿路回溯,每条边恰好被走两次,就能把整棵树的点全部走遍。限制从"一次"放宽到"两次",问题的难度直接从"判定路径"塌缩成"恒真"——这也说明"每条边至多一次"这个条件有多么关键。)