Milad's Lost Tree

Muhimin_Osim The Tough Winter Spar, 20...
Limits 1s, 256 MB

Milad likes trees so much. He has a rooted tree with $n$ vertices each of which has some non-negative value $a_i$ $(1 ≤ i ≤ n)$. One day, he became interested to calculate the path value $sum_i$ $(1 ≤ i ≤ n)$ for each vertex from the root $1$. The path value of a vertex is the summation of values of all vertices in the path. Unfortunately, the next day he lost the values of all vertices. Not only he lost the values of all vertices, but also, he lost some random path values $sum_i$.

More formally, all that Milad has right now are his tree and some path values (all path values can be lost). So, for each of the lost path values $sum_i$ is equal to $-1$. Now, Milad needs your help to retrieve all the values of vertices, $a_i$ such that each of the lost path values can be replaced by some valid values and the summation of values of all vertices is minimum, or determine that he can’t retrieve from the given data.

Input

Input starts with an integer $T (1 ≤ T ≤ 10)$, denoting the number of test cases.

Each case contains an integer $N (2 ≤ N ≤ 10^5)$, denoting the number of vertices in the tree.

The next line contains $N$ integers $sum_i$ $(-1 ≤ sum_i ≤ 10^9)$, denoting the path values for each vertex from the root $1$.

Each of the following $N - 1$ contains two integers $u$ and $v \; (1 \leq u, v \leq N)$ - denoting an edge of the tree.

Output

For each test case, print a line "Case x: y" where $x$ is to be replaced by the test case number and $y$ is to be replaced by the minimum total summation of values of all vertices or $-1$ if you can’t determine the values.

Sample

InputOutput
2
3
4 -1 3
1 2
2 3
4
1 -1 -1 -1
1 2
1 3
1 4
Case 1: -1
Case 2: 1

Submit

Login to submit.

Statistics

82% Solution Ratio
tmwilliamlin168Earliest, Dec '19
tanzim_bnFastest, 0.1s
dragoonLightest, 6.9 MB
user.838823Shortest, 962B
Toph uses cookies. By continuing you agree to our Cookie Policy.