← 返回题目列表

Codeforces · 2035/F

F. 树操作

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

有一天,一只乌龟给了你一棵树,其中有 $$$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$$$ 的子树中。