Milad likes trees so much. He has a rooted tree with vertices each of which has some non-negative value . One day, he became interested to calculate the path value for each vertex from the root . 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 .
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 is equal to . Now, Milad needs your help to retrieve all the values of vertices, 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 starts with an integer , denoting the number of test cases.
Each case contains an integer , denoting the number of vertices in the tree.
The next line contains integers , denoting the path values for each vertex from the root .
Each of the following contains two integers and - denoting an edge of the tree.
For each test case, print a line "Case x: y" where is to be replaced by the test case number and is to be replaced by the minimum total summation of values of all vertices or if you can’t determine the values.
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
Login to submit
First of all, we can't retrieve the data of the tree if a path value for a vertex is less than a pat...