⼩杨寻宝

题目描述

⼩杨有⼀棵包含 个节点的树，树上的⼀些节点放置有宝物。 ⼩杨可以任意选择⼀个节点作为起点并在树上移动，但是⼩杨只能经过每条边⾄多⼀次，当⼩杨经过⼀条边后，这 条边就会消失。⼩杨每经过⼀个放置有宝物的节点就会取得该宝物。 ⼩杨想请你帮他判断⾃⼰能否成功取得所有宝物。

输入格式

第⼀⾏包含⼀个正整数 ，代表测试⽤例组数。 接下来是 组测试⽤例。对于每组测试⽤例，⼀共 ⾏。 第⼀⾏包含⼀个正整数 ，代表树的节点数。 第⼆⾏包含 个⾮负整数 ，其中如果 ，则节点 放置有宝物，若 ，则节点 没有宝物。 之后 ⾏，每⾏包含两个正整数 ，代表存在⼀条连接节点 和 的边。

输出格式

对于每组测试数据，如果⼩杨能成功取得所有宝物，输出 Yes，否则输出 No。 3.1.4 样例1 1 2 2 5 3 0 1 0 1 0 4 1 2 5 1 3 6 3 4 7 3 5 8 5 9 1 1 1 1 1 10 1 2 11 1 3 12 3 4 13 3 5 1 Yes 2 No 对于第⼀组测试⽤例，⼩杨从节点 出发，按照 的顺序即可成功取得所有宝物。 子任务编号 数据点占比 1 20% 2 20% 3 60% 对于全部数据，保证有 ， ，且保证树上⼀定有⾄少⼀个节点放置有宝物。 3.1.5 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 vector g[N]; 5 int col[N],dep[N],has[N]; 6 void dfs(int x,int fa){ 7 dep[x]=dep[fa]+1; 8 for(auto i:g[x]){ 9 if(i!=fa){ 10 dfs(i,x); 11 } 12 } 13 } 14 bool dfs2(int x,int fa){ 15 for(auto i:g[x]){ 16 if(i!=fa){ 17 auto res = dfs2(i,x); 18 if(res==false)return false; 19 if(has[i]||col[i])has[x]++; 20 } 21 } 22 if(has[x]>1)return false; 23 return true; 24 } 25 int main(){ 26 int t; 27 cin>>t; 28 while(t--){ 29 int n; 30 cin>>n; 31 for(int i=1;i<=n;i++){ 32 dep[i]=0;g[i].clear(); 33 cin>>col[i]; 34 } 35 for(int i=1;i<n;i++){ 36 int u,v; 37 cin>>u>>v; 38 g[u].push_back(v); 39 g[v].push_back(u); 40 } 41 dfs(1,0); 42 int mx=0,pos=0; 43 for(int i=1;i<=n;i++){ 44 has[i]=0; 45 if(col[i]){ 46 if(dep[i]>mx){ 47 mx=dep[i]; 48 pos=i; 49 } 50 } 51 } 52 bool res= dfs2(pos,0); 53 if(res)cout<<"Yes\n"; 54 else cout<<"No\n"; 55 } 56 }

样例输入 #1

1 2
2 5
3 0 1 0 1 0
4 1 2
5 1 3
6 3 4
7 3 5
8 5
9 1 1 1 1 1
10 1 2
11 1 3
12 3 4
13 3 5
1 Yes
2 No
对于第⼀组测试⽤例，⼩杨从节点 出发，按照 的顺序即可成功取得所有宝物。
子任务编号 数据点占比
1 20%
2 20%
3 60%

样例输出 #1

数据范围

见题目描述

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。