Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a rooted tree with $N$ nodes (numbered $1$ through $N$); node $1$ is the root. Each node has a value; let's denote the value of node $i$ by $A_{i}$.

You may perform the following operation any number of times (including zero): choose any node which still exists in the tree and remove the whole subtree of this node including itself.

Let's define the *profit* as the sum of values of all nodes which currently exist in the tree minus $X \cdot k$, where $k$ denotes the number of times this operation was performed. Find the maximum possible profit.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $X$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
Each of the following $N-1$ lines contains two space-separated integers $u$ and $v$ denoting that nodes $u$ and $v$ are connected by an edge.

------  Output ------
For each test case, print a single line containing one integer — the maximum profit.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ X ≤ 10^{9}$
$1 ≤ u, v ≤ N$
$|A_{i}| ≤ 10^{9}$ for each valid $i$
the graph described on the input is a tree

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ N ≤ 1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
1

3 5

1 -5 -10

1 2

2 3
----- Sample Output 1 ------ 
-4

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10 ** 5 + 1)
from collections import defaultdict
for _ in range(int(input())):
	(N, X) = list(map(int, input().split()))
	tree = [[] for i in range(N)]
	A = list(map(int, input().split()))
	for i in range(N - 1):
		(u, v) = list(map(int, input().split()))
		u -= 1
		v -= 1
		tree[u] += [v]
		tree[v] += [u]

	def dfs(A, tree, parent, node):
		ans = A[node]
		for i in tree[node]:
			if i != parent:
				ans += dfs(A, tree, node, i)
		return max(ans, -X)
	print(dfs(A, tree, 0, 0))


import sys
sys.setrecursionlimit(100000)
for t in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append([])
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		l[u - 1].append(v - 1)
		l[v - 1].append(u - 1)

	def dfs(ver, parent):
		res = 0
		for kid in l[ver]:
			if kid != parent:
				res += dfs(kid, ver)
		return max(a[ver] + res, -1 * x)
	ans = dfs(0, 0)
	print(ans)


import sys
sys.setrecursionlimit(100000)

def dfs(node, tree, par, X, values):
	res = 0
	for edge in tree[node]:
		if edge == par:
			continue
		res += dfs(edge, tree, node, X, values)
	return max(values[node] + res, -X)
T = int(input())
for _ in range(T):
	(N, X) = tuple(map(int, input().split()))
	values = list(map(int, input().split()))
	tree = [[] for _ in range(N)]
	for _ in range(N - 1):
		(i, j) = tuple(map(int, input().split()))
		tree[i - 1].append(j - 1)
		tree[j - 1].append(i - 1)
	print(dfs(0, tree, -1, X, values))


from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]

def dfs(n, ed, vi, x, arr):
	vi[n] = True
	c = arr[n]
	for i in ed[n]:
		if vi[i] == False:
			dfs(i, ed, vi, x, arr)
			c += arr[i]
	arr[n] = max(-x, c)
for _ in range(ii()):
	(n, x) = il()
	arr = il()
	ed = []
	for k in range(n):
		ed.append([])
	for __ in range(n - 1):
		(u, v) = il()
		ed[u - 1].append(v - 1)
		ed[v - 1].append(u - 1)
	vi = [False] * n
	dfs(0, ed, vi, x, arr)
	print(arr[0])


import sys, threading
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
threading.stack_size(10 ** 8)

def solve(graph, vis, curr, u, a, x):
	vis[u] = True
	curr = a[u - 1]
	for neighbor in graph[u]:
		if vis[neighbor] == False:
			curr += solve(graph, vis, 0, neighbor, a, x)
	return max(curr, -x)
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		d[u].append(v)
		d[v].append(u)
	vis = [False] * (n + 1)
	print(solve(d, vis, 0, 1, a, x))


import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	for _ in range(int(input())):
		(n, x) = map(int, input().split())
		arr = list(map(int, input().split()))
		graph = [[] for _ in range(n)]
		for _ in range(n - 1):
			(a, b) = map(int, input().split())
			a -= 1
			b -= 1
			graph[a].append(b)
			graph[b].append(a)

		def dfs(node, par):
			temp = arr[node]
			for nie in graph[node]:
				if nie != par:
					temp += max(dfs(nie, node), -x)
			return temp
		print(max(dfs(0, -1), -x))
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


import sys, threading
import collections
sys.setrecursionlimit(10 ** 7)
threading.stack_size(10 ** 8)

def dfs(node, parent):
	visited[node] = True
	sum = 0
	for nbr in graph[node]:
		if visited[nbr]:
			continue
		sum += dfs(nbr, node)
	return max(sum + wt[node], -x)
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	wt = list(map(int, input().split()))
	graph = collections.defaultdict(list)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		graph[u].append(v)
		graph[v].append(u)
	visited = [False] * (n + 1)
	ans = dfs(0, 0)
	print(ans)


import sys
sys.setrecursionlimit(10 ** 8)

def dfs(x, parent):
	someSum = values[x]
	for nb in nbs[x]:
		if nb != parent:
			dfs(nb, x)
		someSum += sums[nb]
	sums[x] = max(someSum, cut_cost)
cases = int(input())
for case in range(cases):
	(n, cut_cost) = map(int, input().split())
	cut_cost *= -1
	values = [int(x) for x in input().split()]
	sums = [0 for i in range(n)]
	nbs = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		nbs[a].append(b)
		nbs[b].append(a)
	dfs(0, 0)
	print(sums[0])


import sys, threading
from collections import defaultdict
sys.setrecursionlimit(10 ** 8)
threading.stack_size(10 ** 9)
ip = sys.stdin.readline

def do_dfs(tree, arr, vis, root, par, X):
	tot = 0
	vis[root] = True
	for node in tree[root]:
		if node != par and vis[node] == False:
			tot += do_dfs(tree, arr, vis, node, root, X)
	return max(-X, tot + arr[root - 1])
for _ in range(int(ip())):
	(n, X) = map(int, ip().split())
	arr = list(map(int, ip().split()))
	tree = defaultdict(list)
	for _ in range(n - 1):
		(u, v) = map(int, ip().split())
		tree[u].append(v)
		tree[v].append(u)
	vis = [False] * (n + 1)
	print(do_dfs(tree, arr, vis, 1, -1, X))


import sys, resource
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)

def solve(graph, vis, u, a, x):
	vis[u] = True
	curr = a[u]
	for neighbor in graph[u]:
		if vis[neighbor] == False:
			curr += solve(graph, vis, neighbor, a, x)
	return max(curr, -x)
limit = 10 ** 5 + 5
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.insert(0, 0)
	d = defaultdict(list)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		d[u].append(v)
		d[v].append(u)
	vis = [False] * (n + 1)
	print(solve(d, vis, 1, a, x))


from sys import stdin, stdout
from collections import defaultdict, deque
import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, -1))
sys.setrecursionlimit(10 ** 7)

def dfs(node, parent):
	cost = l[node]
	for x in gp[node]:
		if x != parent:
			dfs(x, node)
	co = 0
	for x in gp[node]:
		if x != parent:
			co += max(-k, dp[x])
	cost = max(cost + co, -k)
	dp[node] = cost

def main():
	try:
		global gp, n, k, dp, l
		(n, k) = In()
		l = [0] + list(In())
		dp = [-float('inf')] * (n + 1)
		gp = defaultdict(list)
		for i in range(n - 1):
			(a, b) = In()
			gp[a].append(b)
			gp[b].append(a)
		dfs(1, 1)
		print(dp[1])
	except:
		pass

def add(a, b, c):
	res = a + b
	if res >= c:
		return res - c
	else:
		return res

def mod(a, b, c):
	res = a * b
	if res >= c:
		return res % c
	else:
		return res

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	w = a // gcd(a, b)
	return w * b

def expo(a, b):
	(x, y) = (1, a)
	while b > 0:
		if b & 1:
			x = x * y
		y = y * y
		b >>= 1
	return x

def power(a, b, m):
	(x, y) = (1,)
	while b > 0:
		if b & 1:
			x = mod(x, y, m)
		y = mod(y, y, m)
		b >>= 1
	return x

def L():
	return list(map(int, stdin.readline().split()))

def In():
	return map(int, stdin.readline().split())

def I():
	return int(stdin.readline())
P = 1000000007
for _ in range(I()):
	main()


from sys import stdin
import sys
sys.setrecursionlimit(10 ** 6)
t = int(stdin.readline())
for _ in range(t):
	(n, x) = map(int, stdin.readline().split())
	a = list(map(int, stdin.readline().split()))
	d = {}
	for i in range(n - 1):
		(p, q) = map(int, stdin.readline().split())
		if p not in d.keys():
			d[p] = [q]
		else:
			d[p].append(q)
		if q not in d.keys():
			d[q] = [p]
		else:
			d[q].append(p)
	vis = [False] * (n + 1)

	def sol(n):
		vis[n] = True
		val = a[n - 1]
		if n in d:
			for i in d[n]:
				if not vis[i]:
					val = max(val - x, val + sol(i))
		return val
	print(max(-x, sol(1)))


import sys
sys.setrecursionlimit(int(1000000.0))

def solve(node, parent):
	ans1 = -x
	ans2 = lis[node]
	check = True
	for child in tree[node]:
		if child != parent:
			check = False
			ans2 += solve(child, node)
	if check:
		return max(ans1, lis[node])
	return max(ans1, ans2)
for t in range(int(input())):
	(n, x) = map(int, input().split())
	from collections import defaultdict
	tree = defaultdict(list)
	lis = [0] + list(map(int, input().split()))
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		tree[u].append(v)
		tree[v].append(u)
	dp = defaultdict(int)
	vis = [False for i in range(n + 1)]
	print(solve(1, None))


from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

def dfs(p, prev):
	(val, su, s) = (0, 0, 0)
	for i in child[p]:
		if i != prev:
			b = dfs(i, p)
			s = (b[0] + a[i - 1]) * -1
			v = max(b[1], s - x)
			val += v
			su += b[0] + a[i - 1]
	return [su, val]
for T in range(int(input())):
	(n, x) = 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)
	b = dfs(1, 0)
	s = (b[0] + a[0]) * -1
	v = max(b[1], s - x)
	print(b[0] + a[0] + v)


import sys
sys.setrecursionlimit(10 ** 5 + 1)

def solve(v, i, g, w, k):
	v[i] = 1
	res = 0
	for j in g[i]:
		if v[j] == 0:
			res += solve(v, j, g, w, k)
	return max(w[i - 1] + res, -k)
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	tre = {}
	for i in range(1, n + 1):
		tre[i] = []
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		tre[a].append(b)
		tre[b].append(a)
	visit = [0 for i in range(n + 1)]
	print(solve(visit, 1, tre, l, x))


import sys
sys.setrecursionlimit(10 ** 5 + 1)

def RW():
	return sys.stdin.readline().strip()

def RI():
	return int(RW())

def RII():
	return [int(x) for x in sys.stdin.readline().strip().split()]

def RWI():
	return [x for x in sys.stdin.readline().strip().split()]
nb_test = RI()
for _ in range(nb_test):
	(nb_nodes, xfactor) = RII()
	wieghts = RII()
	visited = [False] * (nb_nodes + 1)
	adj = [list() for _ in range(nb_nodes + 1)]
	for i in range(nb_nodes - 1):
		(frm, tos) = RII()
		adj[frm].append(tos)
		adj[tos].append(frm)

	def solve(node):
		visited[node] = True
		value = wieghts[node - 1]
		for n in adj[node]:
			if not visited[n]:
				value = max(value - xfactor, value + solve(n))
		return value
	result = max(-xfactor, solve(1))
	print(result)


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

def ish(a, b, c, d):
	s = d[b]
	for i in c[b]:
		if i != a:
			s += ish(b, i, c, d)
	return -min(X, -s)
for i in range(T):
	(N, X) = map(int, input().split())
	d = list(map(int, input().split()))
	t = [[] for i in range(N)]
	for i in range(N - 1):
		(u, v) = map(int, input().split())
		t[u - 1].append(v - 1)
		t[v - 1].append(u - 1)
	print(ish(-1, 0, t, d))


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

def ish(par, me, child, vals):
	s = vals[me]
	for i in child[me]:
		if i != par:
			s += ish(me, i, child, vals)
	return -min(x, -s)
while t:
	(n, x) = map(int, input().split())
	vals = list(map(int, input().split()))
	edges = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		edges[u - 1].append(v - 1)
		edges[v - 1].append(u - 1)
	print(ish(-1, 0, edges, vals))
	t -= 1


import sys
sys.setrecursionlimit(100010)
from collections import defaultdict as d

class Graph:

	def __init__(self, V, l, X):
		self.V = V
		self.adj = d(list)
		self.tr = l
		self.l = d(int)
		for i in range(1, self.V + 1):
			self.l[i] = self.tr[i]
		self.X = X

	def addedge(self, u, v):
		self.adj[u].append(v)
		self.adj[v].append(u)

	def DFS_Util(self, x, visited):
		visited[x] = True
		for i in self.adj[x]:
			if visited[i] == False:
				self.l[x] += self.DFS_Util(i, visited)
		return max(self.l[x], -X)

	def DFS(self, x):
		visited = [False] * (self.V + 1)
		return self.DFS_Util(x, visited)
for _ in range(int(input())):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	l = [0] + A
	g = Graph(N, l, X)
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		g.addedge(a, b)
	print(g.DFS(1))


import sys
sys.setrecursionlimit(10 ** 6)

def maxP(root, Nodes, values, visited, X):
	sumV = 0
	for i in Nodes[root]:
		if visited[i] == 0:
			visited[i] = 1
			sumV += maxP(i, Nodes, values, visited, X)
	return max(values[root] + sumV, -1 * X)
for i in range(int(input())):
	[N, X] = list(map(int, input().split()))
	nodeValues = list(map(int, input().split()))
	Nodes = {0: []}
	visited = [1]
	for j in range(N - 1):
		visited.append(0)
		(u, v) = list(map(int, input().split()))
		try:
			Nodes[u - 1].append(v - 1)
		except:
			Nodes[u - 1] = [v - 1]
		try:
			Nodes[v - 1].append(u - 1)
		except:
			Nodes[v - 1] = [u - 1]
	print(maxP(0, Nodes, nodeValues, visited, X))


from math import gcd
import bisect
import itertools
import sys
from collections import deque
I = lambda : sys.stdin.readline()
mod = 10 ** 9 + 7
sys.setrecursionlimit(1000000)

def modu(a, m):
	if a % m:
		return a % m
	return m

def mindiff(a):
	b = a[:]
	b.sort()
	m = 10000000000
	for i in range(len(b) - 1):
		if b[i + 1] - b[i] < m:
			m = b[i + 1] - b[i]
	return m

def lcm(a, b):
	return a * b // gcd(a, b)

def merge(a, b):
	i = 0
	j = 0
	c = 0
	ans = []
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			ans.append(a[i])
			i += 1
		else:
			ans.append(b[j])
			c += len(a) - i
			j += 1
	ans += a[i:]
	ans += b[j:]
	return (ans, c)

def mergesort(a):
	if len(a) == 1:
		return (a, 0)
	mid = len(a) // 2
	(left, left_inversion) = mergesort(a[:mid])
	(right, right_inversion) = mergesort(a[mid:])
	(m, c) = merge(left, right)
	c += left_inversion + right_inversion
	return (m, c)

def is_prime(num):
	if num == 1:
		return False
	if num == 2:
		return True
	if num == 3:
		return True
	if num % 2 == 0:
		return False
	if num % 3 == 0:
		return False
	t = 5
	a = 2
	while t <= int(math.sqrt(num)):
		if num % t == 0:
			return False
		t += a
		a = 6 - a
	return True

def ceil(a, b):
	if a % b == 0:
		return a // b
	else:
		return a // b + 1

def ncr1(n, r):
	s = 1
	for i in range(min(n - r, r)):
		s *= n - i
		s %= mod
		s *= pow(i + 1, mod - 2, mod)
		s %= mod
	return s

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def getsum(e, val, ver, v):
	if len(e[ver]) == 0:
		val[ver] = v[ver]
		return val[ver]
	if val[ver] != -10 ** 9:
		return val[ver]
	else:
		val[ver] = v[ver]
		for i in e[ver]:
			val[i] = getsum(e, val, i, v)
			val[ver] += val[i]
		return val[ver]

def check(a, i, v, c, vis):
	x = v[i]
	for j in a[i]:
		if vis[j] == 0:
			vis[i] = 1
			x += check(a, j, v, c, vis)
	return max(x, -c)
for _ in range(int(input())):
	(n, xx) = map(int, input().split())
	v = [0] + list(map(int, I().split()))
	a = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(x, y) = map(int, I().split())
		a[x].append(y)
		a[y].append(x)
	if n == 1:
		print(max(-xx, v[1]))
	else:
		vis = [0] * (n + 1)
		vis[1] = 1
		sys.stdout.write(str(check(a, 1, v, xx, vis)) + '\n')


import sys
sys.setrecursionlimit(1000100)
for _ in range(int(input())):
	(non, p) = map(int, input().strip(' ').split(' '))
	t = [list() for i in range(non + 1)]
	wt = list(map(int, input().strip(' ').split(' ')))
	vt = [False] * (non + 1)
	for i in range(non - 1):
		(a, b) = map(int, input().strip(' ').split(' '))
		t[a].append(b)
		t[b].append(a)

	def AN(nd):
		vt[nd] = True
		pt = wt[nd - 1]
		for n in t[nd]:
			if not vt[n]:
				pt = max(pt - p, pt + AN(n))
		return pt
	print(max(-p, AN(1)))


import sys
sys.setrecursionlimit(100000)
ii = lambda : input().strip().split()

def dfs(u, v):
	ret = 0
	for n in adj[u]:
		if n != v:
			ret += dfs(n, u)
	return max(wt[u] + ret, -x)
for _ in range(int(input().strip())):
	(n, x) = map(int, ii())
	wt = [0] + list(map(int, ii()))
	adj = [[] for i in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, ii())
		adj[u].append(v)
		adj[v].append(u)
	print(dfs(1, 0))


import sys
sys.setrecursionlimit(100010)
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	ls = list(map(int, input().split()))
	v = [False] * (n + 1)
	adj = [list() for i in range(n + 1)]
	for _ in range(n - 1):
		(i, j) = map(int, input().split())
		adj[i].append(j)
		adj[j].append(i)

	def dfs(node):
		v[node] = True
		Sum = ls[node - 1]
		for i in adj[node]:
			if not v[i]:
				Sum += dfs(i)
		return max(Sum, -x)
	print(dfs(1))


from collections import defaultdict
import sys
sys.setrecursionlimit(100010)
t = int(input())
for _ in range(t):
	graph = defaultdict(list)

	def addEdge(graph, u, v):
		graph[u].append(v)
		graph[v].append(u)
	(a, b) = input().split()
	n = int(a)
	x = int(b)
	arr = [int(g) for g in input().split()]
	for i in range(n - 1):
		(u, v) = input().split()
		addEdge(graph, int(u), int(v))
	visited = [False] * n

	def subrem(node):
		visited[node - 1] = True
		aver = arr[node - 1]
		for i in graph[node]:
			if not visited[i - 1]:
				aver = max(aver - x, aver + subrem(i))
		return aver
	result = max(-x, subrem(1))
	print(result)


import sys
from collections import defaultdict
sys.setrecursionlimit(100005)

def max_p(root, parent):
	total_profit = 0
	for c in d[root]:
		if c != parent:
			total_profit += max_p(c, root)
	return max(-x, arr[root] + total_profit)
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	d = defaultdict(list)
	arr.insert(0, None)
	for i in range(n):
		d[i + 1] = []
	root = 1
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		d[a].append(b)
		d[b].append(a)
	p = max_p(root, -1)
	print(p)


import sys
sys.setrecursionlimit(100000)

def solve(root, parent):
	value = A[root]
	for u in graph[root]:
		if u != parent:
			value += solve(u, root)
	return max(value, -X)
T = int(input().strip())
for problem in range(1, T + 1):
	(N, X) = list(map(int, input().strip().split()))
	A = [0] + list(map(int, input().strip().split()))
	graph = {u: [] for u in range(1, N + 1)}
	for i in range(N - 1):
		(u, v) = list(map(int, input().strip().split()))
		graph[u].append(v)
		graph[v].append(u)
	print(solve(1, None))


import sys
sys.setrecursionlimit(10 ** 5)

def dfs(v, p):
	s = a[v]
	for u in adj[v]:
		if u != p:
			s += dfs(u, v)
	return max(s, -x)
t = int(input())
for w in range(t):
	adj = {}
	(n, x) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a.insert(0, 0)
	if n == 1:
		if a[1] >= -x:
			print(a[1])
		else:
			print(-x)
	else:
		for q in range(n - 1):
			(c, d) = map(int, input().split())
			if c not in adj:
				adj[c] = [d]
			else:
				adj[c].append(d)
			if d not in adj:
				adj[d] = [c]
			else:
				adj[d].append(c)
		p = dfs(1, -1)
		print(p)


from collections import defaultdict
import sys
sys.setrecursionlimit(100010)

class Graph:

	def __init__(self, V):
		self.V = V
		self.graph = defaultdict(list)

	def add_edge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)

	def dfs(self, u, x, A, visted):
		res = 0
		visted[u - 1] = True
		for v in self.graph[u]:
			if not visted[v - 1]:
				res += self.dfs(v, x, A, visted)
		return max(res + A[u - 1], -x)
for _ in range(int(input())):
	(n, x) = map(int, input().strip().split())
	A = list(map(int, input().strip().split()))
	Tree = Graph(n)
	for i in range(n - 1):
		(u, v) = map(int, input().strip().split())
		Tree.add_edge(u, v)
	visted = n * [False]
	g = Tree.dfs(1, x, A, visted)
	print(g)


import sys
sys.setrecursionlimit(100010)

def maxsum(root):
	visited[root] = True
	cur_sum = A[root - 1]
	for i in maptree[root]:
		if not visited[i]:
			cur_sum = max(cur_sum - X, cur_sum + maxsum(i))
	return cur_sum
T = int(input())
for _ in range(T):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	visited = [False] * (N + 1)
	maptree = {i: [] for i in range(1, N + 1)}
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		maptree[a].append(b)
		maptree[b].append(a)
	print(max(maxsum(1), -X))


import sys
sys.setrecursionlimit(100010)
for _ in range(int(input())):
	(n, x) = map(int, input().strip(' ').split(' '))
	weight = list(map(int, input().strip(' ').split(' ')))
	v = [False] * (n + 1)
	adj = [list() for i in range(n + 1)]
	for i in range(n - 1):
		(i, j) = map(int, input().strip(' ').split(' '))
		adj[i].append(j)
		adj[j].append(i)

	def tree(node):
		v[node] = True
		aver = weight[node - 1]
		for n in adj[node]:
			if not v[n]:
				aver = max(aver - x, aver + tree(n))
		return aver
	result = max(-x, tree(1))
	print(result)


import sys

def max1(a, b):
	if a > b:
		return a
	else:
		return b
sys.setrecursionlimit(500000000)

def dfs(graph, m, N, x, start, pt):
	for edge in graph[start]:
		if edge == pt:
			pass
		else:
			dfs(graph, m, N, x, edge, start)
	m[start] = N[start]
	for i in graph[start]:
		m[start] += m[i]
	m[start] = max1(m[start], -x)
t = int(input())
while t > 0:
	(n, x) = map(int, input().split())
	N = list(map(int, input().split()))
	graph = {k: [] for k in range(n)}
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		graph[u - 1].append(v - 1)
		graph[v - 1].append(u - 1)
	m = [0 for j in range(n)]
	dfs(graph, m, N, x, 0, -1)
	print(m[0])
	t = t - 1


import sys
sys.setrecursionlimit(10 ** 5)

def fix():
	queue = [0]
	while queue != []:
		pil = queue.pop(0)
		for kk in chd[pil]:
			chd[kk].remove(pil)
			queue.append(kk)

def inorder(root):
	ll = len(chd[root])
	if ll == 0:
		return val[root]
	for i in range(ll):
		val[root] = val[root] + max(-k, inorder(chd[root][i]))
	return val[root]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	val = list(map(int, input().split()))
	chd = [[] for j in range(n)]
	for __ in range(n - 1):
		(u, v) = map(int, input().split())
		if u == v:
			continue
		chd[u - 1].append(v - 1)
		chd[v - 1].append(u - 1)
	fix()
	val[0] = inorder(0)
	print(max(val[0], -k))


import sys
sys.setrecursionlimit(1000000000)

def dfs(root, par, value, dic, x):
	sum1 = value[root]
	for i in dic[root]:
		if i != par:
			sum2 = dfs(i, root, value, dic, x)
			sum1 = sum1 + sum2
	return max(sum1, -x)

def f():
	t = int(input())
	while t > 0:
		(n, x) = map(int, input().split())
		l = list(map(int, input().split()))
		a = n - 1
		g = [[] for i in range(n)]
		while a > 0:
			(u, v) = map(int, input().split())
			g[u - 1].append(v - 1)
			g[v - 1].append(u - 1)
			a = a - 1
		l = dfs(0, -1, l, g, x)
		print(l)
		t = t - 1
f()


import sys

def dfs(n):
	sum = 0
	bool[n] = True
	for i in hash[n]:
		if bool[i] == False:
			sum += dfs(i)
	return max(l[n] + sum, -x)
sys.setrecursionlimit(10 ** 5 + 1)
from collections import defaultdict
t = int(sys.stdin.readline())
for _ in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	hash = defaultdict(set)
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		hash[a - 1].add(b - 1)
		hash[b - 1].add(a - 1)
	bool = [False] * n
	sys.stdout.write(str(dfs(0)) + '\n')


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

def dfs(par, me, val, child):
	sum = val[me]
	for i in child[me]:
		if i != par:
			sum += dfs(me, i, val, child)
	return max(-x, sum)
while t:
	t -= 1
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	edge = n - 1
	g = [[] for i in range(n)]
	while edge:
		edge -= 1
		(r, s) = map(int, input().split())
		g[r - 1].append(s - 1)
		g[s - 1].append(r - 1)
	print(dfs(-1, 0, l, g))


import sys
sys.setrecursionlimit(2000100)
p = 0
t = 0
wt = 0
vt = 0

def AN(nd):
	global p
	global t
	global wt
	global vt
	vt[nd] = True
	pt = wt[nd - 1]
	for n in t[nd]:
		if not vt[n]:
			pt = max(pt - p, pt + AN(n))
	return pt

def test():
	global p
	global t
	global wt
	global vt
	(non, p) = map(int, input().strip(' ').split(' '))
	t = [list() for i in range(non + 1)]
	wt = list(map(int, input().strip(' ').split(' ')))
	vt = [False] * (non + 1)
	for i in range(non - 1):
		(a, b) = map(int, input().strip(' ').split(' '))
		t[a].append(b)
		t[b].append(a)
	print(max(-p, AN(1)))
	return 0
t = int(input())
for i in range(t):
	testy = test()


import sys
sys.setrecursionlimit(100010)

def CalcolaAlbero(nodo):
	valore = A[nodo]
	if len(V[nodo]) == 0:
		return max(valore, -X)
	for v in V[nodo]:
		if not Visitati[v]:
			Visitati[v] = True
			valore = max(valore - X, valore + CalcolaAlbero(v))
	return valore
T = int(input())
for t in range(T):
	riga = input().split()
	N = int(riga[0])
	X = int(riga[1])
	riga = input().split()
	A = [int(a) for a in riga]
	V = [[] for x in range(N)]
	for n in range(N - 1):
		riga = input().split()
		riga = [int(a) - 1 for a in riga]
		V[riga[0]].append(riga[1])
		V[riga[1]].append(riga[0])
	nodo = 0
	Visitati = [False for x in range(N)]
	Visitati[0] = True
	print(max(CalcolaAlbero(0), -X))


from sys import setrecursionlimit
setrecursionlimit(100000)

def dfs(u, p):
	global x
	val = arr[u]
	kek = 0
	for v in graph[u]:
		if v == p:
			continue
		tmp = dfs(v, u)
		val += tmp[0]
		kek += tmp[1]
	if val - kek * x < -x:
		return (0, 1)
	return (val, kek)

def main():
	global arr, graph, x
	parent = [0] * 100000
	for _ in range(int(input())):
		(n, x) = map(int, input().split())
		graph = [[] for _ in range(n)]
		arr = list(map(int, input().split()))
		for _ in range(1, n):
			(u, v) = map(int, input().split())
			u -= 1
			v -= 1
			graph[u].append(v)
			graph[v].append(u)
		ans = dfs(0, -1)
		print(ans[0] - x * ans[1])
	return 0
main()


from collections import deque

class Node:

	def __init__(self, key):
		self.key = key
		self.value = key
		self.parent = None
		self.children_sum = 0
		self.adjacent = set()

def bfs(adj_list, number_nodes):
	n = list()
	q = deque()
	parent = [0] * number_nodes
	q.append(0)
	n.append(0)
	visited = set()
	visited.add(0)
	while q:
		x = q.popleft()
		for i in adj_list[x]:
			if i not in visited:
				q.append(i)
				visited.add(i)
				parent[i] = x
				n.append(i)
	return (n, parent)
t = int(input())
while t:
	t -= 1
	(n, x) = map(int, input().split())
	nodes = list()
	flag1 = False
	flag2 = False
	total = 0
	nodes = list(map(int, input().split()))
	adj_list = [set() for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj_list[v - 1].add(u - 1)
		adj_list[u - 1].add(v - 1)
	(node_list, parent_list) = bfs(adj_list, n)
	values = [0] * n
	children_sum = [0] * n
	for i in range(n - 1, 0, -1):
		values[node_list[i]] = max(-x, nodes[node_list[i]] + children_sum[node_list[i]])
		children_sum[parent_list[node_list[i]]] += values[node_list[i]]
	print(max(-x, nodes[0] + children_sum[0]))


import sys
sys.setrecursionlimit(100000)

def postord(tree, arr, ind, parent, x):
	v = arr[ind - 1]
	try:
		for i in tree[ind]:
			if i != parent:
				v += postord(tree, arr, i, ind, x)
	except:
		pass
	return max(v, -x)
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	tree = {}
	arr = list(map(int, input().split()))
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		try:
			tree[u].append(v)
		except:
			tree[u] = [v]
		try:
			tree[v].append(u)
		except:
			tree[v] = [u]
	print(postord(tree, arr, 1, -1, x))


import sys
sys.setrecursionlimit(100010)
for _ in range(int(input())):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	Visited = [False] * (N + 1)
	adj = [list() for i in range(N + 1)]
	for i in range(N - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)

	def tree(node):
		Visited[node] = True
		nodeValue = A[node - 1]
		for n in adj[node]:
			if not Visited[n]:
				nodeValue = max(nodeValue - X, nodeValue + tree(n))
		return nodeValue
	result = max(-X, tree(1))
	print(result)


import sys
sys.setrecursionlimit(200000)

def f(x, a, b, y, c):
	l = b[x]
	d = 0
	c[x] = 1
	for i in range(len(l)):
		if c[l[i]] == 1:
			continue
		d += f(l[i], a, b, y, c)
	if d + a[x] < y * -1:
		return y * -1
	else:
		return d + a[x]
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = [[] for x in range(n)]
	c = [0] * n
	for i in range(n - 1):
		(x, y) = [int(k) for k in input().split()]
		b[x - 1].append(y - 1)
		b[y - 1].append(x - 1)
	print(f(0, a, b, m, c))


import sys
sys.setrecursionlimit(1000000)
from collections import defaultdict

def get_cost_grid(adj_map, val_map, X):
	root = 1

	def DFS(root, parent):
		sum = val_map[root - 1]
		for child in adj_map[root]:
			if child != parent:
				sum += DFS(child, root)
		return max(sum, -X)
	return DFS(root, -root)

def main():
	try:
		test_cases = int(input())
		while test_cases:
			dict = defaultdict(list)
			(N, X) = [int(i) for i in input().split()]
			nums = [int(i) for i in input().split()]
			counter = N - 1
			while counter:
				(node1, node2) = [int(i) for i in input().split()]
				dict[node1].append(node2)
				dict[node2].append(node1)
				counter -= 1
			if N == 1:
				if nums[0] < -1 * X:
					print(str(-1 * X))
				else:
					print(str(nums[0]))
			else:
				x = get_cost_grid(dict, nums, X)
				print(str(x))
			test_cases -= 1
	except:
		print('Error')
main()


import sys
sys.setrecursionlimit(1500000)

def dp(adj, v, par, x):
	res = wt[v - 1]
	for i in adj[v]:
		if i != par:
			res += dp(adj, i, v, x)
	return max(-x, res)
T = int(input())
for t in range(T):
	(n, x) = map(int, input().strip(' ').split(' '))
	wt = list(map(int, input().strip(' ').split(' ')))
	adj = [list() for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = map(int, input().strip(' ').split(' '))
		adj[a].append(b)
		adj[b].append(a)
	print(dp(adj, 1, 1, x))


import sys
sys.setrecursionlimit(10 ** 5)

def fun():
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	g = {x: [] for x in range(1, n + 1)}
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)

	def dfs(p, v):
		s = a[v - 1]
		for u in g[v]:
			if u != p:
				s += dfs(v, u)
		return max(s, -x)
	print(dfs(0, 1))
for _ in range(int(input())):
	fun()


import sys
sys.setrecursionlimit(10 ** 5)
t = int(input())

def tree(node):
	visited[node] = True
	res = weight[node - 1]
	for i in adjacencyList[node]:
		if not visited[i]:
			res = max(res - x, res + tree(i))
	return res
while t:
	t -= 1
	(n, x) = map(int, input().strip().split())
	weight = list(map(int, input().strip().split()))
	visited = [False] * (n + 1)
	adjacencyList = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().strip().split())
		adjacencyList[u].append(v)
		adjacencyList[v].append(u)
	y = tree(1)
	print(max(-x, y))


import sys
sys.setrecursionlimit(100100)

class Graph:

	def __init__(self):
		self.Graph = [[] * i for i in range(n + 10)]

	def add_edge_between(self, u, v):
		self.Graph[u].append(v)
		self.Graph[v].append(u)

	def subtree_sum_again_with_vertex(self, v):
		visited[v] = True
		for i in self.Graph[v]:
			if not visited[i]:
				self.subtree_sum_again_with_vertex(i)
				value_of_node[v] = value_of_node[v] + value_of_node[i]
		if value_of_node[v] <= x:
			value_of_node[v] = x
for _ in range(int(input())):
	(n, y) = map(int, input().split())
	value_of_node = [0] + list(map(int, input().split()))
	x = -1 * y
	g = Graph()
	for _ in range(n - 1):
		(edge1, edge2) = map(int, input().split())
		g.add_edge_between(edge1, edge2)
	visited = [False] * (n + 10)
	g.subtree_sum_again_with_vertex(1)
	print(value_of_node[1])
	del visited, g, value_of_node, n, y, x


t = int(input())
while t > 0:
	parent = []
	child = []
	visited = []
	bfs = []
	neighbour = []
	(n, x) = map(int, input().split())
	for i in range(n + 1):
		neighbour.append(list())
		parent.append(0)
		visited.append(0)
		child.append(list())
	values = list(map(int, input().split()))
	values.insert(0, 0)
	for i in range(n - 1):
		(p, q) = map(int, input().split())
		neighbour[p].append(q)
		neighbour[q].append(p)
	neighbour[0] = [1]
	neighbour[1].append(0)
	i = 0
	j = 0
	current = [0]
	visited[0] = 1
	while i <= n:
		for v in neighbour[j]:
			if visited[v] == 0:
				visited[v] = 1
				current.append(v)
				parent[v] = j
				child[j].append(v)
		i += 1
		if i != n + 1:
			j = current[i]
		else:
			j = current[i - 1]
	i = n
	while i >= 1:
		if values[current[i]] < 0 and -values[current[i]] >= x:
			values[parent[current[i]]] -= x
		else:
			values[parent[current[i]]] += values[current[i]]
		i -= 1
	print(values[0])
	t -= 1


import sys

def dfs(b, c, a, x, s, p):
	for i in b[s]:
		if i != p:
			dfs(b, c, a, x, i, s)
	c[s] = a[s]
	for i in b[s]:
		c[s] += c[i]
	if c[s] <= -x:
		c[s] = -x
sys.setrecursionlimit(3000000)
t = int(input())
for t1 in range(t):
	(n, x) = [int(j) for j in input().split()]
	a = [int(j) for j in input().split()]
	b = {i: [] for i in range(0, n)}
	for i in range(n - 1):
		(u, v) = [int(j) for j in input().split()]
		b[u - 1].append(v - 1)
		b[v - 1].append(u - 1)
	c = [0 for j in range(n)]
	dfs(b, c, a, x, 0, -1)
	print(c[0])


import sys
sys.setrecursionlimit(100010)
for _ in range(int(input())):
	(n, x) = map(int, input().strip(' ').split(' '))
	w = list(map(int, input().strip(' ').split(' ')))
	v = [False] * (n + 1)
	tree = [list() for i in range(n + 1)]
	for i in range(n - 1):
		(i, j) = map(int, input().strip(' ').split(' '))
		tree[i].append(j)
		tree[j].append(i)

	def beta(node):
		v[node] = True
		agg = w[node - 1]
		for n in tree[node]:
			if not v[n]:
				agg = max(agg - x, agg + beta(n))
		return agg
	print(max(-x, beta(1)))


import sys
sys.setrecursionlimit(100010)
for _ in range(int(input())):
	(nnn, x) = map(int, input().strip(' ').split(' '))
	ttt = [list() for i in range(nnn + 1)]
	www = list(map(int, input().strip(' ').split(' ')))
	vvv = [False] * (nnn + 1)
	for i in range(nnn - 1):
		(u, v) = map(int, input().strip(' ').split(' '))
		ttt[u].append(v)
		ttt[v].append(u)

	def alpha(node):
		vvv[node] = True
		profit = www[node - 1]
		for n in ttt[node]:
			if not vvv[n]:
				profit = max(profit - x, profit + alpha(n))
		return profit
	print(max(-x, alpha(1)))


for test in range(int(input())):
	(n, k) = map(int, input().split())
	l1 = []
	l2 = [0] * n
	l4 = []
	for n1 in range(n):
		l1.append([])
	l3 = input().split()
	for j in range(len(l3)):
		l3[j] = int(l3[j])
	for j in range(n - 1):
		(x, y) = map(int, input().split())
		l1[x - 1].append(y)
		l1[y - 1].append(x)
		l2[x - 1] = l2[x - 1] + 1
		l2[y - 1] = l2[y - 1] + 1
	for l21 in range(1, len(l2)):
		if l2[l21] == 1:
			l4.append(l21)
	for x in range(n - 1):
		l41 = l4[x]
		l1[l1[l41][0] - 1].remove(l41 + 1)
		if l3[l41] < -k:
			l3[l41] = -k
		l3[l1[l41][0] - 1] = l3[l1[l41][0] - 1] + l3[l41]
		if len(l1[l1[l41][0] - 1]) == 1:
			if l1[l41][0] != 1:
				l4.append(l1[l41][0] - 1)
	if l3[0] < -k:
		l3[0] = -k
	print(l3[0])


from collections import defaultdict

class Solution:

	def __init__(self, graph, root, values):
		self.graph = graph
		self.root = root
		self.values = values
		self.tree = defaultdict(list)
		self.max_scores = [None for i in range(len(values))]

	def max_score(self):
		node = 1
		stack = [node]
		visited = set()
		while stack:
			node = stack[-1]
			if node in visited:
				acum = 0
				for child in self.graph[node]:
					acum += self.max_scores[child - 1] if self.max_scores[child - 1] is not None else 0
				self.max_scores[node - 1] = max(-x, acum + self.values[node - 1])
				stack.pop()
			else:
				for child in self.graph[node]:
					if child not in visited:
						stack.append(child)
				visited.add(node)
		return self.max_scores[self.root - 1]
t = int(input())
ans = []
for i in range(t):
	(n, x) = [int(s) for s in input().split(' ') if s != '']
	a = [int(s) for s in input().split(' ') if s != '']
	graph = defaultdict(list)
	for i in range(n - 1):
		(u, v) = [int(s) for s in input().split(' ') if s != '']
		graph[u].append(v)
		graph[v].append(u)
	root = 1
	solution = Solution(graph, root, a)
	ans.append(solution.max_score())
for i in range(t):
	print(ans[i])