← 返回题目列表

Codeforces · 1592/C

C. Bakry 和分区

中文机器翻译题面 查看原题

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$$$。