F. Tree Operations
binary search; brute force; dfs and similar; dp; trees
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\).