#1890. [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。

样例

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