题目描述

某国有 $n$ 座城市，编号为 $1$ 到 $n$，以及连接这些城市的 $n-1$ 条双向道路。第 $j$ 条道路连接城市 $u_j,v_j$。最初，任意两座城市之间都可以通过若干条道路互相到达。

现在计划对全部道路进行改造。改造后，每条道路将处于以下四种状态之一：

1. 双向通行：可以从 $u_j$ 到 $v_j$，也可以从 $v_j$ 到 $u_j$。
2. 仅允许从 $u_j$ 到 $v_j$ 的单向通行。
3. 仅允许从 $v_j$ 到 $u_j$ 的单向通行。
4. 关闭：两个方向均不允许通行。

如果存在城市序列 $c_1,c_2,\ldots,c_k$，满足 $c_1=u$、$c_k=v$，且对于所有 $x$（$1\le x<k$），均有一条允许从 $c_x$ 通行到 $c_{x+1}$ 的道路，则称城市 $u$ 可以到达城市 $v$。特别地，每座城市都可以到达自身。

改造计划不慎遗失了。第 $i$ 座城市的市长声称，改造后从该城市出发能够到达的城市数量为 $l_i$，但这些数值可能有误。

你需要判断，是否存在一种道路改造方案，使得所有市长所说的数值都正确。

输入格式

输入的第一行包含一个正整数 $T$，表示数据组数。

接下来依次给出 $T$ 组数据，每组的格式如下：

第一行包含一个正整数 $n$，表示城市数量。

第二行包含 $n$ 个正整数 $l_1,l_2,\ldots,l_n$，依次表示各市长声称的可到达城市数量。

接下来 $n-1$ 行，其中第 $j$ 行包含两个正整数 $u_j,v_j$，表示第 $j$ 条道路连接的两座城市。

输出格式

对于每组数据，输出一行一个字符串。若存在满足要求的改造方案，则输出 YES；否则输出 NO。

输入输出样例

2
2
2 2
1 2
3
2 2 2
1 2
2 3

YES
NO

说明/提示

样例 1 解释

第一组数据中，保留唯一一条双向道路，两座城市均能到达两座城市，因此输出 YES。

第二组数据中，相邻城市的数值相等，道路只能双向通行或关闭。三座城市无法划分为大小均为 $2$ 的连通块，因此输出 NO。

该样例满足测试点 $1\sim4$ 的约束条件。

样例 2

见附件中的 reach/reach2.in 与 reach/reach2.ans。

该样例满足测试点 $5\sim7$ 的约束条件。

样例 3

见附件中的 reach/reach3.in 与 reach/reach3.ans。

该样例满足测试点 $1\sim4$ 的约束条件。

数据范围

对于所有测试数据，均有：

• $1\le T\le10$，每组数据满足 $1\le n\le5000$，同一测试点内所有组的 $n$ 之和不超过 $40000$；
• 对于所有 $i$（$1\le i\le n$），均有 $1\le l_i\le n$；
• 对于所有 $j$（$1\le j<n$），均有 $1\le u_j,v_j\le n$，且 $u_j\ne v_j$；
• 所有道路构成一棵树。

下表中的限制对对应测试点内的每一组数据均成立。每个测试点 $5$ 分。

测试点编号	$n\le$	特殊性质
$1\sim4$	$7$	无
$5\sim7$	$15$
$8\sim10$	$5000$	A
$11\sim14$		B
$15\sim17$	$400$	无
$18\sim20$	$5000$

特殊性质 A：$l_1=l_2=\cdots=l_n$。

特殊性质 B：如果存在满足要求的改造方案，则至少存在一种满足要求且不包含双向道路的改造方案。

附件

下载附加样例（reach.zip）