GESP 七级¶

P11249 [GESP202409 七级] 小杨寻宝 ¶

本题解由陈奕涵提供

题意：
我们有一棵 n 个节点的树，某些节点上有宝物。
小杨从任意一个节点出发，每条边只能走一次，走过就消失。
每经过一个宝物节点就能得到宝物。
问能否一次性拿到所有宝物。

提示

1.每条边只能走一次，所以路径不能重复。

2.因为树是连通的，所以从任意起点出发，可以走到任意节点，但走过的边消失后，不能再跨过已消失的边。

3.因此，走过的路径一定是条简单路径（可以延伸、拐弯，但不能重复边）。

提示2

假设宝物节点集合为 S。

如果 S = 1，显然 Yes（直接走到那个点）。

如果 S = 2，那么这两个宝物节点之间的唯一路径必须能一次走完，显然可以（从其中一个走到另一个）。

如果 S = 3，就要考虑更多。

提示3

1.读入 n 和宝物标记数组a.

2.建树。

3.如果宝物节点数量小于2，直接输出 Yes。

否则：

4.任选一个宝物节点 s，BFS找到离它最远的宝物节点u。

5.从u 出发，BFS 找到离它最远的宝物节点 v。

6.得到路径 u -> v（记录路径上的所有节点）。

7.检查所有宝物节点是否都在 u -> v 的路径上。

8.如果是，输出 Yes，否则输出 No。

代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;

vector<int> g[MAXN];
int a[MAXN];
int n;

pair<int, int> bfs(int start) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    int farthest = start, maxDist = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] && dist[i] > maxDist) {
            maxDist = dist[i];
            farthest = i;
        }
    }
    return {farthest, maxDist};
}

bool check() {
    vector<int> treasures;
    for (int i = 1; i <= n; i++) {
        if (a[i]) treasures.push_back(i);
    }
    if (treasures.size() <= 2) return true;

    int u = treasures[0];
    int v = bfs(u).first;

    // 第二次 BFS 从 v 出发，记录 parent 用于找路径
    vector<int> dist(n + 1, -1), parent(n + 1, -1);
    queue<int> q;
    dist[v] = 0;
    q.push(v);

    while (!q.empty()) {
        int uu = q.front();
        q.pop();
        for (int w : g[uu]) {
            if (dist[w] == -1) {
                dist[w] = dist[uu] + 1;
                parent[w] = uu;
                q.push(w);
            }
        }
    }

    // 找到离 v 最远的宝物节点 u2
    int u2 = v, maxDist = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] && dist[i] > maxDist) {
            maxDist = dist[i];
            u2 = i;
        }
    }

    // 标记 u2 -> v 路径上的所有节点
    vector<bool> onPath(n + 1, false);
    int cur = u2;
    while (cur != -1) {
        onPath[cur] = true;
        cur = parent[cur];
    }

    // 检查所有宝物节点是否都在路径上
    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++) {
            g[i].clear();
            cin >> a[i];
        }
        for (int i = 0; i < n - 1; i++) {
            int x, y;
            cin >> x >> y;
            g[x].push_back(y);
            g[y].push_back(x);
        }

        if (check()) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}

GESP 七级¶

P11249 [GESP202409 七级] 小杨寻宝¶

P11249 [GESP202409 七级] 小杨寻宝 ¶