Pku2054 Color a Tree

时间限制:1s      空间限制:64MB

题目描述


输入格式

The input consists of several test cases. The first line of each case contains two integers N and R (1 <= N <= 1000, 1 <= R <= N), where N is the number of nodes in the tree and R is the node number of the root node. The second line contains N integers, the i-th of which is Ci (1 <= Ci <= 500), the coloring cost factor of node i. Each of the next N-1 lines contains two space-separated node numbers V1 and V2, which are the endpoints of an edge in the tree, denoting that V1 is the father node of V2. No edge will be listed twice, and all edges will be listed. A test case of N = 0 and R = 0 indicates the end of input, and should not be processed.


输出格式

For each test case, output a line containing the minimum total coloring cost required for Bob to color all the nodes.


样例输入

5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
0 0


样例输出

33

提示

没有写明提示


题目来源

没有写明来源