1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#!/usr/bin/env python3
from collections import defaultdict
for t in range(int(input())):
n, x = map(int, input().split())
a, edges = [int(i) for i in input().split()], defaultdict(list)
for _ in range(1, n):
u, v = (int(i) - 1 for i in input().split())
edges[u].append(v)
edges[v].append(u)
queue, parents, walked = [0], [0] * n, [not i for i in range(n)]
for i in queue:
for j in edges[i]:
if walked[j]: continue
walked[j], parents[j] = 1, i
queue.append(j)
net, profit = a.copy(), a.copy()
queue.reverse()
queue.pop()
for i in queue:
parent, profit[i] = parents[i], max(net[i], -x, profit[i])
net[parent] += net[i]
profit[parent] += profit[i]
print(max(net[0], -x, profit[0]))
|
