Bakry 遇到了一个问题,但由于他懒于解决它,所以他请求你的帮助。
给定一个由 $$$n$$$ 节点组成的树,从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$ 为第 $$$i$$$ 个节点分配了值 $$$a_i$$$。提醒一下,$$$n$$$ 节点上的树是具有 $$$n-1$$$ 边的连通图。
您想要从树中删除至少 $$$1$$$,但最多 $$$k-1$$$ 边,以便满足以下条件:
- 对于每个连接的组件,计算其中节点值的按位异或。然后,所有连接的组件的这些值必须相同。
这个条件可以实现吗?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 和 $$$u_i$$$ 之间有一条边$$$v_i$$$。
保证给定的图是一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,您应该输出一个字符串。如果根据上面写的条件可以删除边,则输出“YES”(不带引号)。否则,输出“NO”(不带引号)。
您可以以任何大小写(大写或小写)打印“YES”和“NO”的每个字母。
示例
输入 #1
5 2 2 1 3 1 2 5 5 3 3 3 3 3 1 2 2 3 1 4 4 5 5 2 1 7 2 3 5 1 2 2 3 1 4 4 5 5 3 1 6 4 1 2 1 2 2 3 1 4 4 5 3 3 1 7 4 1 2 2 3
输出 #1
NO YES NO YES NO
注意
可以证明,对于第一、第三和第五个测试用例,反对意见是无法实现的。
在第二个测试用例中,您可以删除所有边缘。将有 $$$5$$$ 连接的组件,每个组件仅包含一个值为 $$$3$$$ 的节点,因此所有这些组件的按位异或将为 $$$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$$$。