题目背景

2024 年 9 月 GESP C++ 七级编程第 1 题

题目描述

小杨有一棵包含 $n$ 个节点的树，部分节点放有宝物。他可以任选一个节点作为起点在树上移动，但每条边最多经过一次；经过一条边后，这条边就会消失。经过放有宝物的节点即可取得该宝物。

请判断小杨是否存在一种行走方式，能够取得所有宝物。

输入格式

第一行输入正整数 $t$，表示测试组数。 每组数据第一行输入正整数 $n$。 第二行输入 $n$ 个整数 $a_1,a_2,ldots,a_n$，$a_i=1$ 表示节点 $i$ 有宝物，$a_i=0$ 表示没有。 接下来 $n-1$ 行，每行输入两个正整数 $x_i,y_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

数据范围与提示

• $1 \le t\le 10$，$1 \le n\le 10^5$。
• 所有测试组的 $n$ 之和不超过 $10^5$。
• 能一次不重复边地经过所有宝物，等价于包含所有宝物的最小连通子树中奇度点数量不超过 $2$。

来源

GESP 2024 年 09 月 C++ 七级 T1