CF1592C.Bakry and Partitioning

Bakry faced a problem, but since he's lazy to solve it, he asks for your help.

You are given a tree of $n$ nodes, the $i$-th node has value $a_i$ assigned to it for each $i$ from $1$ to $n$. As a reminder, a tree on $n$ nodes is a connected graph with $n-1$ edges.

You want to delete at least $1$, but at most $k-1$ edges from the tree, so that the following condition would hold:

• For every connected component calculate the bitwise XOR of the values of the nodes in it. Then, these values have to be the same for all connected components.

Is it possible to achieve this condition?

巴克里遇到了一个问题，但由于他懒得解决，所以他向你求助。

给你一棵包含 $n$ 个节点的树，对每个 $i$（从 $1$ 到 $n$），第 $i$ 个节点被赋予一个值 $a_i$。需要提醒的是：$n$ 个节点上的树是一个具有 $n-1$ 条边的连通图。

你希望从该树中删除至少 $1$ 条、至多 $k-1$ 条边，使得以下条件成立：

• 对每个连通分量，计算其中所有节点的值的按位异或（XOR）；然后，所有连通分量所得到的这些 XOR 值必须彼此相等。

能否实现这一条件？

Each test contains multiple test cases. The first line contains the number of test cases $t$ $(1 \leq t \leq 5 \cdot 10^4)$. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ $(2 \leq k \leq n \leq 10^5)$.

The second line of each test case contains $n$ integers $a_1, a_2, ..., a_n$ $(1 \leq a_i \leq 10^9)$.

The $i$-th of the next $n-1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i\neq v_i$), which means that there's an edge between nodes $u_i$ and $v_i$.

It is guaranteed that the given graph is a tree.

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

每个测试包含多个测试用例。第一行包含测试用例数量 $t$ $(1 \leq t \leq 5 \cdot 10^4)$。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ $(2 \leq k \leq n \leq 10^5)$。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ $(1 \leq a_i \leq 10^9)$。

接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i\neq v_i$)，表示节点 $u_i$ 与 $v_i$ 之间存在一条边。

保证所给图是一棵树。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, you should output a single string. If you can delete the edges according to the conditions written above, output "YES" (without quotes). Otherwise, output "NO" (without quotes).

You can print each letter of "YES" and "NO" in any case (upper or lower).

对于每个测试用例，你应该输出一个字符串。如果你能按照上述条件删除边，则输出 "YES"（不带引号）；否则，输出 "NO"（不带引号）。

你可以以任意大小写（大写或小写）输出 "YES" 和 "NO" 中的每个字母。

It can be shown that the objection is not achievable for first, third, and fifth test cases.

In the second test case, you can just remove all the edges. There will be $5$ connected components, each containing only one node with value $3$, so the bitwise XORs will be $3$ for all of them.

In the fourth test case, this is the tree: .

You can remove an edge $(4,5)$

The bitwise XOR of the first component will be, $a_1 \oplus a_2 \oplus a_3 \oplus a_4 = 1 \oplus 6 \oplus 4 \oplus 1 = 2$ (where $\oplus$ denotes the bitwise XOR).

The bitwise XOR of the second component will be, $a_5 = 2$.

可以证明，该要求在第一、第三和第五个测试用例中无法实现。

在第二个测试用例中，你可以直接删除所有边。此时将得到 $5$ 个连通分量，每个分量仅包含一个权值为 $3$ 的节点，因此所有分量的按位异或（XOR）结果均为 $3$。

在第四个测试用例中，该树如下所示：。

你可以删除边 $(4,5)$。

第一个连通分量的按位异或值为 $a_1 \oplus a_2 \oplus a_3 \oplus a_4 = 1 \oplus 6 \oplus 4 \oplus 1 = 2$（其中 $\oplus$ 表示按位异或运算）。

第二个连通分量的按位异或值为 $a_5 = 2$。