有一天,一只乌龟给了你一棵树,其中有 $$$n$$$ 个节点,根节点为 $$$x$$$。每个节点都有一个初始非负值;第 $$$i$$$ 个节点的起始值为 $$$a_i$$$。
您想让所有节点的值等于$$$0$$$。为此,您将对树执行一系列操作,其中每个操作将在某个节点上执行。将节点 $$$u$$$ 上的操作定义为在 $$$u$$$ 的子树$$$^{\text{*}}$$$ 中选择单个节点,并将其值递增或递减 $$$1$$$。对节点的操作顺序如下:
- 对于 $$$1 \le i \le n$$$,将在节点 $$$i$$$ 上执行第 $$$i$$$ 操作。
- 对于 $$$i > n$$$,第 $$$i$$$ 操作将在与操作 $$$i - n$$$ 相同的节点上执行。
更正式地说,第 $$$i$$$ 个操作将在第 $$$(((i - 1) \bmod n) + 1)$$$ 个节点上执行。$$$^{\text{†}}$$$
请注意,您不能跳过操作;也就是说,如果不首先执行操作 $$$1, 2, \ldots, i - 1$$$,则无法执行第 $$$i$$$ 操作。
假设您选择最佳操作,则找到使所有节点的值等于 $$$0$$$ 之前必须执行的最少操作数。如果有限次运算后无法使所有节点的值都等于$$$0$$$,则输出$$$-1$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 2000$$$, $$$1 \le x \le n$$$) — 节点数和树的根数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) - 每个节点的起始值。
每个测试用例接下来的 $$$n - 1$$$ 行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$),表示从 $$$u$$$ 到 $$$v$$$ 的无向边。保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。
输出
对于每个测试用例,输出一个整数,表示使所有节点 $$$0$$$ 所需的最小操作量。如果不可能使所有节点$$$0$$$,则输出$$$-1$$$。
示例
输入 #1
5 2 1 1 2 1 2 3 2 2 1 3 2 1 3 2 4 1 1 1 0 1 1 2 2 3 1 4 12 6 14 4 5 6 12 9 5 11 6 2 1 12 3 9 10 6 6 12 4 3 3 1 5 11 9 7 5 6 1 8 2 8 5 1 1 1 0
输出 #1
3 6 5 145 0
注意
在第一个测试用例中,您可以进行以下有效的操作序列:
- 对于操作 $$$1$$$,减少节点 $$$1$$$ 的值。这是有效的,因为 $$$(((1 - 1) \bmod n) + 1) = 1$$$,并且节点 $$$1$$$ 位于节点 $$$1$$$ 的子树中。
- 对于操作 $$$2$$$,减少节点 $$$2$$$ 的值。这是有效的,因为 $$$(((2 - 1) \bmod n) + 1) = 2$$$,并且节点 $$$2$$$ 位于节点 $$$2$$$ 的子树中。
- 对于操作 $$$3$$$,减少节点 $$$2$$$ 的值。这是有效的,因为 $$$(((3 - 1) \bmod n) + 1) = 1$$$,并且节点 $$$2$$$ 位于节点 $$$1$$$ 的子树中。