Click Here!

Alice and Bob have invented a new game. They have a rooted tree having NN nodes (rooted at node 11), and the ithith node has the value AiAi associated with it (11-indexed). The value associated with the root node is 00.

They start with a marker at the root node, and a score of 00. Alice and Bob moves alternatively, with Alice moving first. In one move, they can move the pointer from a node to one of its child node, and add the value associated with that child node to the score. If the marker reaches a leaf node, the game ends.

Alice wants to minimize the score of the game, whereas Bob wants to maximize the score. They were about to start the game when the Charlie arrives. He looked at the game, and declared the game to be boring. However, Charlie asked them – “What will be the score at the end of the game, if eacheach one of you can skip at mostat most KK moves?”

Can you help Alice and Bob to answer Charlie?

The Minimum Game solution codechef

• The first line of input contains a single integer TT, denoting the number of testcases. The description of the TT testcases follows.
• The first line of each test case contains two space separated integers NN and KK.
• The second line of each test case contains NN space separated integers A1,A2,...,ANA1,A2,…,AN. It is guaranteed that A1=0A1=0.
• The following N1N−1 lines contains two space separated integers xx and yy, which denotes that there is an edge between nodes xx and yy.

Output Format

For each testcase, output in a single line the answer to the Charlie’s problem.

The Minimum Game solution codechef

• 1T1041≤T≤104
• 1N1051≤N≤105
• 0K2000≤K≤200
• 109Ai109−109≤Ai≤109
• 1x,yN1≤x,y≤N
• The sum of NN over all test cases does not exceed 105105

The Minimum Game solution codechef

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


Sample Output 1

1
2
6


Explanation

Test Case 11: Alice can move the marker to node 22, and hence making score =1=1. If Alice skips her chance, then Bob can move the marker to node 33, and hence making score = 22. Therefore, Alice will not skip her chance.

Test Case 22: If Alice moves the marker to node 22, then Bob will move the marker to node 44, making score = 44. If Alice moves the marker to node 33, the game will end, and the score will be 22.