CF2035F Tree Operations

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

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

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

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