G7008 [GESP202409 七级] 小杨寻宝 题解

知识点：树、拓扑剥叶、路径判定。

解题思路

从无宝藏叶节点开始剥除无关枝条，剩余子树是连接所有宝藏的最小子树。检查其每个点度数不超过2，即可判断是否能在一条简单路径上收集全部宝藏。

为什么正确

树中连接指定节点的路径唯一，所有必需节点都在该最小子树；连通树能成为一条路径当且仅当无度数大于2的分叉。

易错点

不能一开始删除所有无宝藏节点，它们可能是必要的中转点；必须按叶子逐步剥除。

复杂度

每组时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        vector<int>a(n+1),deg(n+1),dead(n+1);
        for(int i=1;i<=n;i++)cin>>a[i];
        vector<vector<int>>g(n+1);
        for(int i=1;i<n;i++) {
            int u,v;
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        queue<int>q;
        for(int i=1;i<=n;i++) {
            deg[i]=g[i].size();
            if(deg[i]<=1&&!a[i])q.push(i);
        }
        while(!q.empty()) {
            int u=q.front();
            q.pop();
            if(dead[u])continue;
            dead[u]=1;
            for(int v:g[u])if(!dead[v]&&--deg[v]<=1&&!a[v])q.push(v);
        }
        bool ok=true;
        for(int i=1;i<=n;i++)if(!dead[i]&&deg[i]>2)ok=false;
        cout<<(ok?"Yes":"No")<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。