每条边至多走一次 ⟺ 走的必然是一条简单路径;问题化为"所有宝物是否落在同一条路径上"。
小杨有一棵包含 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) |
| 起点 | 任意选择;只需判断可行性,不用输出路径 |
Nocnt[v] > 0 算一个方向;u 的父节点一侧若有宝物(即 tot − cnt[u] > 0)再算一个方向。方向数 ≥ 3 就输出 No宝物在节点 2 和节点 4,共 2 个。以 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
方向 = 一个儿子子树(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] | 儿子中含宝物的方向数 | 父方向有宝物? | 方向总数 |
|---|---|---|---|---|
| 1 | 2 | 儿子 2、3(2 个) | 2 − 2 = 0 → 否 | 2 |
| 2 | 1 | 无儿子 | 2 − 1 = 1 → 是 | 1 |
| 3 | 1 | 儿子 4(1 个,5 不含) | 2 − 1 = 1 → 是 | 2 |
| 4 | 1 | 无儿子 | 2 − 1 = 1 → 是 | 1 |
| 5 | 0 | 无儿子 | 2 − 0 = 2 → 是 | 1 |
2 − 1 − 3 − 4:正好把宝物 2、4 串在一条线里。注意宝物数目 tot = 2 时,任意两个点之间都有一条路径,所以 tot ≤ 2 的情况答案一定是 Yes。这次 5 个节点全都是宝物,tot = 5。
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
节点 3 的儿子 4、5 都含宝物 → 2 个方向
父方向 tot − cnt[3] = 5 − 3 = 2 > 0 → 再加 1 个
方向总数 = 2 + 1 = 3 ≥ 3
这意味着宝物分散在 3 条互不重合的方向上
❌ 3 ≥ 3 → No
| 经过节点 3 的路径 | 能覆盖的方向 | 漏掉的宝物 |
|---|---|---|
| 4 − 3 − 5 | 儿子 4、儿子 5 两个方向 | 节点 1、2(父方向) |
| 4 − 3 − 1(−2) | 儿子 4 + 父方向 | 节点 5 |
| 5 − 3 − 1(−2) | 儿子 5 + 父方向 | 节点 4 |
| 不经过节点 3 的路径 | 至多落在一个方向内 | 另外两个方向全漏 |
以 1 为根一次 DFS 求出 cnt,检查每个节点的含宝物方向数是否 ≥ 3
任取宝物 s,BFS 找最远宝物 a;再从 a BFS 找最远宝物 b,最后验证每个宝物都在 a↔b 上
dist(a, x) + dist(x, b) == dist(a, b)。| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 子树计数 + 方向判据 | O(n) | 约 35 行 |
| 两次 BFS 求点集直径 | O(n) | 约 60 行 |
| 枚举路径 / 模拟所有行走 | 指数级 | ❌ 不可行 |
按题目格式输入一棵小树(第一行 n,第二行 n 个 0/1,之后 n−1 行每行一条边),程序会用"子树宝物计数 + 方向数判据"给出 Yes / No,并列出每个节点的 cnt 与方向数。
点按钮开始 →
#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; }
| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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 组数据共用全局数组,不清空会串数据 |
g[i].clear())导致跨组污染;③ 把"方向数 ≥ 3"写成"度数 ≥ 3"——度数 3 但只有一个方向含宝物是完全合法的;④ 求 cnt 时用正序遍历(父亲还没拿到儿子的值)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
2 | Yes No | 题面样例(两组) |
1 | Yes | 只有一个节点、只有一个宝物 |
1 | Yes | 两个宝物分居中心两侧,方向数恰好 2 |
1 | No | 菊花:中心有 3 个含宝物方向 |
1 | Yes | n = 2 的最小 Yes |
1 | Yes | 链的两端是宝物,中间无宝物 |
1 | Yes | 链上隔位放宝物 |
1 | No | 宝物分布在两个分支上 |
1 | Yes | 分支上恰好没有宝物 |
1 | Yes | tot = 1 恒为 Yes |
tot − cnt[u] 判吗?④ 每组都清空图了吗?邻接表存 2(n − 1) 条无向边(约 2 × 10⁵ 个 int),再加 cnt / par / vis / order 四个长度 n 的数组。
✅ 每组线性,t ≤ 10 时总运算量约 3 × 10⁶,1 s 内轻松通过,而且完全不依赖 n 的形态(链、菊花、随机树都一样快)。
// 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"判据 | 判断点集能否被一条路径覆盖 | 树的直径、点覆盖问题、路径覆盖最小条数 |
| 迭代 DFS | n = 10⁵ 时不爆栈 | 所有深树遍历、拓扑排序、强连通分量 |
| 多组数据清空 | t ≤ 10 组共用全局数组 | 一切多测题目(尤其是清空 vector) |