CF2035F.Tree Operations

这确实反映了我们的社会。

有一天，一只乌龟给了你一棵树，共 $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$ 第1次操作。

假设您选择了最优的操作，找到在使所有节点的值等于 $0$ 之前必须执行的最小操作数。如果经过有限次运算，不可能使所有节点的值都等于 $0$ ，则输出 $-1$ 。

$^{\text{∗}}$ 节点 $u$ 的子树是 $u$ 位于从该节点到根节点的最短路径上的节点集合，包括 $u$ 本身。

$^{\text{†}}$ 这里， $a \bmod b$ 表示 $a$ 除以 $b$ 的余数。

第一行包含单个整数 $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$，减少节点 $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$ 的子树中。

翻译者 wjbbssb250；WangBX 修缮一些细节。