# Tree Operations

## Problem Description

This really says a lot about our society.



One day, a turtle gives you a tree with $ n $ nodes rooted at node $ x $ . Each node has an initial nonnegative value; the $ i $ -th node has starting value $ a_i $ .

You want to make the values of all nodes equal to $ 0 $ . To do so, you will perform a series of operations on the tree, where each operation will be performed on a certain node. Define an operation on node $ u $ as choosing a single node in $ u $ 's subtree $ ^{\text{∗}} $ and incrementing or decrementing its value by $ 1 $ . The order in which operations are performed on nodes is as follows:

- For $ 1 \le i \le n $ , the $ i $ -th operation will be performed on node $ i $ .
- For $ i > n $ , the $ i $ -th operation will be performed on the same node as operation $ i - n $ .

More formally, the $ i $ -th operation will be performed on the $ (((i - 1) \bmod n) + 1) $ -th node. $ ^{\text{†}} $

Note that you cannot skip over operations; that is, you cannot perform the $ i $ -th operation without first performing operations $ 1, 2, \ldots, i - 1 $ .

Find the minimum number of operations you must perform before you can make the values of all nodes equal to $ 0 $ , assuming you pick operations optimally. If it's impossible to make the values of all nodes equal to $ 0 $ after finite operations, output $ -1 $ .

 $ ^{\text{∗}} $ The subtree of a node $ u $ is the set of nodes for which $ u $ lies on the shortest path from this node to the root, including $ u $ itself.

 $ ^{\text{†}} $ Here, $ a \bmod b $ denotes the remainder from dividing $ a $ by $ b $ .

## Input Format

The first line contains a single integer $ t $ ( $ 1\le t\le 100 $ ) — the number of test cases.

The first line of each test case contains two integers $ n $ and $ x $ ( $ 1 \le n \le 2000 $ , $ 1 \le x \le n $ ) — the number of nodes and the root of the tree.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) — the starting value of each node.

Each of the next $ n - 1 $ lines of each test case contains two integers $ u $ and $ v $ ( $ 1 \le u, v \le n $ , $ u \neq v $ ) representing an undirected edge from $ u $ to $ v $ . It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2000 $ .

## Output Format

For each test case, output a single integer denoting the minimum amount of operations needed to make all nodes $ 0 $ . If it's impossible to make all nodes $ 0 $ , output $ -1 $ .

## Sample #1

### Sample Input #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
```

### Sample Output #1

```
3
6
5
145
0
```

## Hint

In the first test case, you can make the following valid sequence of operations:

- For operation $ 1 $ , decrease the value of node $ 1 $ . This is valid because $ (((1 - 1) \bmod n) + 1) = 1 $ , and node $ 1 $ is in the subtree of node $ 1 $ .
- For operation $ 2 $ , decrease the value of node $ 2 $ . This is valid because $ (((2 - 1) \bmod n) + 1) = 2 $ , and node $ 2 $ is in the subtree of node $ 2 $ .
- For operation $ 3 $ , decrease the value of node $ 2 $ . This is valid because $ (((3 - 1) \bmod n) + 1) = 1 $ , and node $ 2 $ is in the subtree of node $ 1 $ .

## Limit



Time Limit
4.00s

Memory Limit
250.00MB

Tags: binary search, brute force, dfs and similar, dp, trees
Difficulty: 2500