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

[GESP202409 七级] 小杨寻宝

Description

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

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

⼩杨想请你帮他判断⾃⼰能否成功取得所有宝物。

Input Format

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

接下来是 tt 组测试⽤例。对于每组测试⽤例,⼀共 n+1n+1 ⾏。

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

第⼆⾏包含 个⾮负整数 a1,a2,...,ana_1,a_2,...,a_n,其中如果 ai=1a_i=1 ,则节点 ii 放置有宝物,若 ai=0a_i=0,则节点 ii 没有宝物。

之后 n1n-1 ⾏,每⾏包含两个正整数 xi,yix_i,y_i,代表存在⼀条连接节点 xix_iyiy_i 的边。

Output Format

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

Hint

样例解释

对于第⼀组测试⽤例,⼩杨从节点 22 出发,按照 21342-1-3-4 的顺序即可成功取得所有宝物。

数据范围

子任务编号 数据点占比 tt nn
1 20%20\% 10\leq 10 5\leq 5
2 20%20 \% 10\leq 10 1000\leq 1000
3 60%60\% 10\leq 10 105\leq 10^5

对于全部数据,保证有 1t10,1n1051 \leq t \leq 10 , 1 \leq n \leq 10^50ai10 \leq a_i \leq 1,且保证树上⼀定有⾄少⼀个节点放置有宝物。

Source

GESP七级202409