#1908. Pku2054 Color a Tree

题目描述

输入格式

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  

数据范围与提示