D. Tree Merger
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes. At first, the value of the $$$i$$$-th node is $$$a_i$$$.

The two nodes can be merged only if the following two conditions hold:

  1. The values of the two nodes are equal;
  2. They are connected by an edge.

In the $$$i$$$-th merging, a new node with number $$$(n+i)$$$ is created. Assume we'll merge node $$$x$$$ and $$$y$$$, we set the value of node $$$(n+i)$$$ to the sum of the value of node $$$x$$$ and $$$y$$$, and we add edges of node $$$(n+i)$$$ and all the nodes connected to node $$$x$$$ and $$$y$$$, except $$$x$$$ and $$$y$$$ themselves. After that, node $$$x$$$ and $$$y$$$ will be removed.

Find if it's possible to merge all nodes into one node.

Input

The first line contains a single integer $$$t(1 \le t\le 10^4)$$$ — the number of test cases.

The first line of each test case contains a single number $$$n$$$($$$2\le n\le 2 \cdot 10^5$$$).

The next line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n(1\le a_i\le 10^9)$$$  — the value on the $$$i$$$-th node.

The next $$$n-1$$$ lines contain two integers $$$u_i$$$,$$$v_i$$$($$$1\le u_i,v_i\le n$$$)  —the numbers of nodes connected by the $$$i$$$-th edge. It is guaranteed that the input forms a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output YES if it's possible to merge all nodes into one node.Otherwise, output NO.

You can output the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will be recognized as positive responses.

Example
Input
5
5
8 1 1 2 4
1 2
2 3
3 4
3 5
4
3 3 3 3
1 2
2 3
2 4
4
3 3 3 3
1 2
2 3
3 4
2
1 2
1 2
5
1 1 1 4 1
1 2
2 3
2 4
1 5
Output
YES
NO
YES
NO
YES
Note

In the first test case, the initial tree is shown in the following picture:

In the first merging, we merge node $$$2$$$ and node $$$3$$$ to obtain the new node $$$6$$$.

In the second merging, we merge node $$$4$$$ and node $$$6$$$ to obtain the new node $$$7$$$.

In the third merging, we merge node $$$5$$$ and node $$$7$$$ to obtain the new node $$$8$$$.

In the fourth merging, we merge node $$$1$$$ and node $$$8$$$ to obtain the new node $$$9$$$.

In the second test case, it's impossible to merge all nodes into one node.