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 nn vertices each of which has some non-negative value aia_i (1in)(1 ≤ i ≤ n). One day, he became interested to calculate the path value sumisum_i (1in)(1 ≤ i ≤ n) for each vertex from the root 11. 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 sumisum_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 sumisum_i is equal to 1-1. Now, Milad needs your help to retrieve all the values of vertices, aia_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(1T10)T (1 ≤ T ≤ 10), denoting the number of test cases.

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

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

Each of the following N1N - 1 contains two integers uu and v  (1u,vN)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 xx is to be replaced by the test case number and yy is to be replaced by the minimum total summation of values of all vertices or 1-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


85% Solution Ratio

tmwilliamlin168Earliest, Dec '19

CodefresherFastest, 0.2s

dragoonLightest, 6.9 MB

serotoninShortest, 963B

Submit

Login to submit

Editorial

First of all, we can't retrieve the data of the tree if a path value for a vertex is less than a pat...

Related Contests