Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Milad's Lost Tree

By Muhimin_Osim · 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

Discussion

Statistics


88% Solution Ratio

tmwilliamlin168Earliest, 1M ago

tmwilliamlin168Fastest, 0.2s

dragoonLightest, 6.9 MB

serotoninShortest, 963B

Submit

Login to submit

Related Contests

The Tough Winter Spar, 2019 Ended at 2020-01-04 12:00:00 +0000 UTC