2024-09 · 7级 · 小杨寻宝

GESP 标程 · 考级真题 · 代码 · cpp · 难度 5/5 · 共 1428 字

CCF 原卷官方标程 · 数组与向量、位运算、搜索、栈与队列 · 本地编译通过

2024-09
数组与向量

正文

// GESP 2024-09 C++ 7级 编程题 1 · 小杨寻宝
// 原题：https://oj.yecheng.tv/p/gs2409l7p1
// 官方原卷：https://gesp.ccf.org.cn/101/attach/1633836324618272.pdf
// 题意：小杨有一棵包含个节点的树，树上的一些节点放置有宝物。
// 知识点：数组与向量、位运算、搜索、栈与队列
// 参考程序：CCF 原卷官方标程，PDF 抽取后已去行号；本地编译核验通过，供打字练习
// 原卷样例验证：样例验证 1/1 通过
//
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int> g[N];
int col[N],dep[N],has[N];
void dfs(int x,int fa){
    dep[x]=dep[fa]+1;
    for(auto i:g[x]){
        if(i!=fa){
            dfs(i,x);
        }
    }
}
bool dfs2(int x,int fa){
    for(auto i:g[x]){
        if(i!=fa){
            auto res = dfs2(i,x);
            if(res==false)return false;
            if(has[i]||col[i])has[x]++;
        }
    }
    if(has[x]>1)return false;
    return true;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            dep[i]=0;g[i].clear();
            cin>>col[i];
        }
        for(int i=1;i<n;i++){
            int u,v;
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1,0);
        int mx=0,pos=0;
        for(int i=1;i<=n;i++){
            has[i]=0;
            if(col[i]){
                if(dep[i]>mx){
                    mx=dep[i];
                    pos=i;
                }
            }
        }
        bool res= dfs2(pos,0);
        if(res)cout<<"Yes\n";
        else cout<<"No\n";
    }
}

2024-09 · 7级 · 小杨寻宝

正文

GESP 标程 · 考级真题的其它内容