#G1073. [GESP202409 七级] 小杨寻宝

[GESP202409 七级] 小杨寻宝

[GESP202409 七级] 小杨寻宝

题目描述

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

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

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

输入格式

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

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

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

第二行包含 nn 个非负整数 a1,a2,…,ana_1, a_2, \dots, a_n,其中如果 ai=1a_i = 1,则节点 ii 放置有宝物,若 ai=0a_i = 0,则节点 ii 没有宝物。

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

Yes
No

样例解释

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

数据范围

子任务编号 数据点占比 tt nn
1 20% ≤10≤ 10 ≤5≤ 5
2 ≤1000≤ 1000
3 60% ≤105≤ 10^5
  • 对于全部数据,保证有 1≤t≤101 ≤ t ≤ 10,1≤n≤1051 ≤ n ≤ 10^5,0≤ai≤10 ≤ a_i ≤ 1,且保证树上一定有至少一个节点放置有宝物。