企业官网建设流程全解析

1. 题目分析

本题给定一棵包含 n 个节点的树，部分节点放置有宝物。小杨从任意节点出发，每条边至多经过一次（经过后边消失），问能否取得所有宝物。

由于每条边只能走一次，小杨的路径本质上是一条简单路径（不重复经过边）。因此问题转化为：是否存在一条简单路径，能够覆盖所有放置宝物的节点。

2. 核心思路

在树中，一条简单路径能覆盖的节点集合，其关键性质是：所有宝物节点必须位于同一条路径上。等价地，从任意一个宝物节点出发，到其他所有宝物节点的路径，都必须经过同一条「主干路径」。

更简洁的判定方法：所有宝物节点中，度数（在宝物节点构成的虚树中）大于 2 的节点不能超过 2 个。换句话说，宝物节点必须形成一条链。

3. 判定方法

具体做法如下：

1. 找出所有宝物节点。
2. 任选一个宝物节点作为起点，找到离它最远的宝物节点 u（通过 DFS 求距离）。
3. 再从 u 出发，找到离 u 最远的宝物节点 v。
4. 检查从 u 到 v 的这条路径是否覆盖了所有宝物节点。若覆盖，则输出 Yes，否则输出 No。

这是因为：如果所有宝物节点都在同一条路径上，那么「最远点对」的两端 u、v 之间的路径必然覆盖全部宝物节点。

4. 复杂度分析

每组测试数据需要做两次 DFS 或 BFS，时间复杂度为 O(n)，空间复杂度为 O(n)。对于 n ≤ 105、t ≤ 10 的数据规模，完全可行。

5. C++ 参考代码

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; vector<int> g[MAXN]; int a[MAXN]; int n; // DFS 求从 start 出发到所有节点的距离，返回最远宝物节点及其距离 pair<int, int> dfs(int start, int parent, int dist) { pair<int, int> best = {start, dist}; if (!a[start]) best.second = -1; // 非宝物节点不作为候选 for (int v : g[start]) { if (v == parent) continue; auto res = dfs(v, start, dist + 1); if (res.second > best.second) best = res; } return best; } // 检查从 u 到 v 的路径是否覆盖所有宝物节点 bool check(int u, int v) { // 记录路径上的节点 vector<int> path; // 用父节点数组回溯路径 vector<int> parent(n + 1, -1); queue<int> q; q.push(u); parent[u] = 0; while (!q.empty()) { int cur = q.front(); q.pop(); if (cur == v) break; for (int nxt : g[cur]) { if (parent[nxt] == -1) { parent[nxt] = cur; q.push(nxt); } } } // 从 v 回溯到 u int cur = v; while (cur != 0) { path.push_back(cur); cur = parent[cur]; } // 检查所有宝物节点是否都在路径上 vector<bool> onPath(n + 1, false); for (int node : path) onPath[node] = true; for (int i = 1; i <= n; i++) { if (a[i] && !onPath[i]) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; g[i].clear(); } for (int i = 0; i < n - 1; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } // 找到任意一个宝物节点作为起点 int start = 1; for (int i = 1; i <= n; i++) { if (a[i]) { start = i; break; } } // 第一次 DFS：找到离 start 最远的宝物节点 u auto p1 = dfs(start, 0, 0); int u = p1.first; // 第二次 DFS：找到离 u 最远的宝物节点 v auto p2 = dfs(u, 0, 0); int v = p2.first; // 检查 u 到 v 的路径是否覆盖所有宝物 if (check(u, v)) cout << "Yes\n"; else cout << "No\n"; } return 0; }

6. 样例验证

以样例第一组数据为例：宝物节点为 2 和 4。从节点 2 出发，最远宝物节点是 4，路径 2-1-3-4 覆盖了所有宝物节点，因此输出 Yes。

第二组数据中所有 5 个节点都有宝物，宝物节点形成的是「Y」形结构（节点 3 连接 1、4、5），无法用一条简单路径覆盖全部节点，因此输出 No。

7. 总结

本题的核心在于将「能否取得所有宝物」转化为「所有宝物节点是否位于同一条简单路径上」。通过两次 DFS 找到最远宝物点对，再验证路径覆盖，即可在 O(n) 时间内完成判定。