简答题 偏难
#20861

小杨寻宝 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有一棵包含 n 个节点的树,树上的一些节点放置有宝物。 小杨可以任意选择一个节点作为起…

小杨寻宝

时间限制:1.0 s

内存限制:512.0 MB

题面描述

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

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

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

输入格式

第一行包含一个正整数 t ,代表测试用例组数。

接下来是 t 组测试用例。对于每组测试用例,一共 n+1 行。

第一行包含一个正整数 n ,代表树的节点数。

第二行包含 n 个非负整数a1,a2,...,an,其中如果 ai=1,则节点 i 放置有宝物,若ai=0,则节点 i 没有宝物。

之后 n−1 行,每行包含两个正整数xi,yi,代表存在一条连接节点xi和yi的边。

输出格式

对于每组测试数据,如果小杨能成功取得所有宝物,输出 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

对于第一组测试用例,小杨从节点 2 出发,按照2−1−3−4 的顺序即可成功取得所有宝物。

对于全部数据,保证有1≤t≤10,1≤n≤105,0≤ai≤1,且保证树上一定有至少一个节点放置有宝物。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5+10; vector&lt;int&gt; 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]&gt;1)return false; return true; } int main(){ int t; cin&gt;&gt;t; while(t--){ int n; cin&gt;&gt;n; for(int i=1;i&lt;=n;i++){ dep[i]=0;g[i].clear(); cin&gt;&gt;col[i]; } for(int i=1;i&lt;n;i++){ int u,v; cin&gt;&gt;u&gt;&gt;v; g[u].push_back(v); g[v].push_back(u); } dfs(1,0); int mx=0,pos=0; for(int i=1;i&lt;=n;i++){ has[i]=0; if(col[i]){ if(dep[i]&gt;mx){ mx=dep[i]; pos=i; } } } bool res= dfs2(pos,0); if(res)cout&lt;&lt;"Yes\n"; else cout&lt;&lt;"No\n"; } }</pre>
解析

通过题意初步可以想到以每一个点作为起点进行搜索,再搜索过程中记录搜到的ai=1的点,搜索结束后比较和1的总数是否相同。由于数据范围较大,因此明显会超时。

由于每个节点只能走一次,所以可以从最深的宝物开始收集可以确保小杨在返回时不会重复经过已经消失的边(因为边会在经过一次后消失)。然后从这个节点回到根节点,如果是1那么就标记走了一次,如果这里被标记两次那么肯定是不满足题目要求。