Game On the Tree

Given a tree, a connected graph that contains N vertexes and N−1 edges, you should control a virtual miner to get maximum values by walking from a vertex A and stopping at a vertex B.

On a tree, as we know, there is only one road between every two vertexes. Here, you are allowed to choose a vertex A (the value of A can not be 0) and a vertex B by yourself. Walking from A and stopping at B, you must collect all the values on the road. Each vertex has a value. Try to get values as large as you can. Remember that the miner you controlled, can never go back to any vertex he has passed.

However, there is a special way to calculate total values. Let’s assume that the miner has passed M vertexes from A to B. During the travel, the miner has successively collected M values worths Wi (0≤i<M). Vertex A has a value worth WM−1. The next vertex on the road has a value worth WM−2 ...... At last, vertex B has a value worth W0. The special rule gives you an integer P. The total value you collect is calculated by the formula MAX=∑m−1i=0(Wi×Pi).

It is guaranteed that Wi (0≤i<M) are less than P. The vertex A and B you choose can be same. But the value of A can not be 0. Output MAX module (109+7). Note that you need to make sure MAX as large as possible but NOT make sure the remainder as large as possible. And then, output value of each vertex (stating from vertex A) on the road in the best case.

The first line contains an integer T(1≤T≤200), indicating the number of test cases.
For each case, The first and second line contain two integers N (1≤N≤104) and P (2≤P≤109), indicating the number of vertexes and the integer P.

Each of the following N−1 lines contains two integers a and b (1≤a,b≤N,a≠b), indicating that there is an edge connecting vertex a and vertex b.

The following line contains N integers Wi (0≤Wi<P,∑Wi>0), the value of each vertex. It is guaranteed that at least one of Wi not equal 0.

You can assume that sum of N does not exceed 1.3×106.

For each case, the first line outputs "Case #T: MAX"(without quotes). Here, T is the index of test case (starting from 1) and MAX is the maximum value of treasures the miner can collect module (109+7).

The second line outputs the value of each vertex from vertex A to vertex B.

2

8
2
1 2
2 3
3 4
4 5
2 6
6 7
7 8
1 0 0 0 0 0 0 0

9
1000000000
1 2
2 3
1 4
4 5
1 6
6 7
1 8
8 9
1 2 0 2 0 2 0 2 0

Case #1: 16
1 0 0 0 0
Case #2: 999999356
2 1 2 0

2015 Multi-University Training Contest 7