秦皇岛市网站建设_网站建设公司_SQL Server_seo优化

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：P11249 [GESP202409 七级] 小杨寻宝 - 洛谷

【题目描述】

小杨有一棵包含n nn个节点的树，树上的一些节点放置有宝物。

小杨可以任意选择一个节点作为起点并在树上移动，但是小杨只能经过每条边至多一次，当小杨经过一条边后，这条边就会消失。小杨每经过一个放置有宝物的节点就会取得该宝物。

小杨想请你帮他判断自己能否成功取得所有宝物。

【输入】

本题单个测试点内有多组测试数据。输入第一行包含一个正整数t tt，代表测试用例组数。
接下来是t tt组测试用例。对于每组测试用例，一共n + 1 n+1n+1行。

第一行包含一个正整数n nn，代表树的节点数。
第二行包含n nn个非负整数a 1 , a 2 , … a n a_1, a_2, \dots a_na1​,a2​,…an​，其中如果a i = 1 a_i = 1ai​=1，则节点i ii放置有宝物；若a i = 0 a_i = 0ai​=0，则节点i ii没有宝物。
之后n − 1 n - 1n−1行，每行包含两个正整数x i , y i x_i, y_ixi​,yi​，代表存在一条连接节点x i x_ixi​和y i y_iyi​的边。

【输出】

对于每组测试数据，如果小杨能成功取得所有宝物，输出 Yes，否则输出 No。

【输入样例】

2 5 0 1 0 1 0 1 2 1 3 3 4 3 5 5 1 1 1 1 1 1 2 1 3 3 4 3 5

【输出样例】

Yes No

【算法标签】

《洛谷 P11249 小杨寻宝》 #图论# #GESP# #2024#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005,M=N*2;intT;// 测试用例数量intn,a[N],root;// n: 节点数, a[i]: 节点i的初始值, root: 根节点inth[N],e[M],ne[M],idx;// 邻接表存储树boolflag;// 标志位，表示当前树是否合法// 添加无向边voidadd(inta,intb){e[idx]=b;ne[idx]=h[a];h[a]=idx++;}// 深度优先搜索// u: 当前节点// fa: 父节点voiddfs(intu,intfa){if(!flag)return;// 如果已经发现不合法，直接返回intres=0;// 记录子节点值的和// 遍历所有子节点for(inti=h[u];i!=-1;i=ne[i]){intj=e[i];// 子节点if(j==fa)// 跳过父节点{continue;}// 递归处理子节点dfs(j,u);// 累加子节点的值res+=a[j];}// 如果子节点的和不为0，将当前节点设为1if(res){a[u]=1;}// 检查约束条件if((u==root&&res>2)||(u!=root&&res>1)){flag=0;// 不满足条件，标记为非法}}intmain(){cin>>T;// 读取测试用例数while(T--){cin>>n;// 读取节点数// 初始化邻接表memset(h,-1,sizeof(h));idx=0;root=0;flag=1;// 初始假设树是合法的// 读取每个节点的初始值for(inti=1;i<=n;i++){cin>>a[i];}// 找到值为1的节点作为根节点for(inti=1;i<=n;i++){if(a[i]==1){root=i;break;}}// 读取树的边for(inti=1;i<n;i++){intu,v;cin>>u>>v;add(u,v);add(v,u);}// 从根节点开始DFSdfs(root,0);// 输出结果if(flag){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}return0;}

【运行结果】

2 5 0 1 0 1 0 1 2 1 3 3 4 3 5 5 1 1 1 1 1 1 2 1 3 Yes 3 4 3 5 No