Alice and Bob have invented a new game. They have a rooted tree having N nodes (rooted at node 1), and the i^{th} node has the value A_{i} associated with it (1-indexed). The value associated with the root node is 0.

They start with a marker at the root node, and a score of 0. 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 \textbf{each} one of you can skip \textbf{at most} K moves?"

Can you help Alice and Bob to answer Charlie?

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of testcases. The description of the T testcases follows.
- The first line of each test case contains two space separated integers N and K.
- The second line of each test case contains N space separated integers A_{1}, A_{2},..., A_{N}. It is guaranteed that A_{1} = 0.
- The following N-1 lines contains two space separated integers x and y, which denotes that there is an edge between nodes x and y.

------ Output Format ------ 

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

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ K ≤ 200$
$-10^{9} ≤ A_{i} ≤ 10^{9}$
$1 ≤ x, y ≤ N$
- The sum of $N$ over all test cases does not exceed $10^{5}$
 
----- Sample Input 1 ------ 
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 1 ------ 
Test Case $1$: Alice can move the marker to node $2$, and hence making score $= 1$. If Alice skips her chance, then Bob can move the marker to node $3$, and hence making score = $2$. Therefore, Alice will not skip her chance.

Test Case $2$: If Alice moves the marker to node $2$, then Bob will move the marker to node $4$, making score = $4$. If Alice moves the marker to node $3$, the game will end, and the score will be $2$.

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Tree algorithms

Dynamic programming

Game theory

Data structures
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def dfs(p, prev, turn):
	(m1, m2) = (float('inf'), -float('inf'))
	for i in child[p]:
		if i == prev:
			continue
		x = dfs(i, p, turn ^ 1)
		m1 = min(m1, x + a[p - 1])
		m2 = max(m2, x + a[p - 1])
	if p != 1 and len(child[p]) == 1 or len(child[p]) == 0:
		return a[p - 1]
	else:
		return m2 if turn else m1
for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		child[u].append(v)
		child[v].append(u)
	print(dfs(1, -1, 0))


import math
import sys
sys.setrecursionlimit(1000000)

def solve(A, tree, root, dic):
	if root in tree:
		for node in tree.get(root):
			solve(A, tree, node, dic)
	if root not in tree:
		dic[root] = (0, 0)
	else:
		minn = 1000000007
		maxx = -1000000007
		for node in tree.get(root):
			minn = min(minn, A[node] + dic.get(node)[1])
			maxx = max(maxx, A[node] + dic.get(node)[0])
		dic[root] = (minn, maxx)

def buildTree(edges):
	tree = {}
	for edge in edges:
		edge.sort()
		if edge[0] not in tree:
			tree[edge[0]] = [edge[1]]
		else:
			tree[edge[0]].append(edge[1])
	return tree
for t in range(int(input())):
	(N, K) = map(int, input().split())
	dic = {}
	A = list(map(int, input().split()))
	if N == 1:
		print(A[0])
		continue
	edges = []
	for i in range(N - 1):
		(x, y) = map(int, input().split())
		edges.append([x - 1, y - 1])
	tree = buildTree(edges)
	solve(A, tree, 0, dic)
	print(dic[0][0])


T = int(input())
import sys
sys.setrecursionlimit(10000000)

class Node:

	def __init__(self, weight):
		self.weight = int(weight)
		self.cost = None
		self.child = []
		self.level = None
		self.choice = None

def setLevels(node, level=0):
	node.level = level
	for n in node.child:
		setLevels(n, level + 1)

def setCost(node, cost=0):
	node.cost = cost + node.weight
	for n in node.child:
		setCost(n, node.cost)

def findChoice(node):
	if not node.child:
		node.choice = node.cost
		return node.choice
	options = [findChoice(n) for n in node.child]
	if node.level % 2:
		node.choice = max(options)
	else:
		node.choice = min(options)
	return node.choice
for _ in range(T):
	(n, k) = list(map(int, input().split(' ')))
	weights = list(map(Node, input().split(' ')))
	for x in range(n - 1):
		(a, b) = sorted([x - 1 for x in map(int, input().split(' '))])
		weights[a].child.append(weights[b])
	setLevels(weights[0])
	setCost(weights[0])
	findChoice(weights[0])
	print(weights[0].choice)


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 8)

def dfs(p, prev, turn):
	(m1, m2) = (float('inf'), -float('inf'))
	count = 0
	for i in child[p]:
		if i == prev:
			continue
		x = dfs(i, p, turn ^ 1)
		m1 = min(m1, x + a[p - 1])
		m2 = max(m2, x + a[p - 1])
		count += 1
	if count == 0:
		return a[p - 1]
	elif turn == 0:
		return m1
	else:
		return m2
for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		child[u].append(v)
		child[v].append(u)
	ans = dfs(1, -1, 0)
	print(ans)