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 $W_{i}$ $(0 \leq i < M)$. Vertex A has a value worth $W_{M-1}$. The next vertex on the road has a value worth $W_{M-2}$ ...... At last, vertex B has a value worth $W_{0}$. The special rule gives you an integer $P$. The total value you collect is calculated by the formula $MAX = \sum_{i = 0}^{m-1}(W_i \times P^i)$.

It is guaranteed that $Wi$ $(0 \leq 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 $(10^9 + 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 \leq T \leq 200)$, indicating the number of test cases.
For each case, The first and second line contain two integers $N$ $( 1 \leq N \leq 10^4 )$ and $P$ $( 2 \leq P \leq 10^9)$, indicating the number of vertexes and the integer $P$.

Each of the following $N-1$ lines contains two integers $a$ and $b$ $(1 \leq a, b \leq N, a \neq b)$, indicating that there is an edge connecting vertex $a$ and vertex $b$.

The following line contains $N$ integers $W_i$ $( 0 \leq W_i < P, \sum W_i > 0)$, the value of each vertex. It is guaranteed that at least one of $W_i$ not equal 0.

You can assume that sum of $N$ does not exceed $1.3 \times 10^6$.

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 $(10^9 + 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

UESTC

2015 Multi-University Training Contest 7