You are given a weighted tree consisting of $n$ vertices. Recall that a tree is a connected graph without cycles. Vertices $u_i$ and $v_i$ are connected by an edge with weight $w_i$.

You are given $m$ queries. The $i$-th query is given as an integer $q_i$. In this query you need to calculate the number of pairs of vertices $(u, v)$ ($u < v$) such that the maximum weight of an edge on a simple path between $u$ and $v$ doesn't exceed $q_i$.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of vertices in the tree and the number of queries.

Each of the next $n - 1$ lines describes an edge of the tree. Edge $i$ is denoted by three integers $u_i$, $v_i$ and $w_i$ — the labels of vertices it connects ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) and the weight of the edge ($1 \le w_i \le 2 \cdot 10^5$). It is guaranteed that the given edges form a tree.

The last line of the input contains $m$ integers $q_1, q_2, \dots, q_m$ ($1 \le q_i \le 2 \cdot 10^5$), where $q_i$ is the maximum weight of an edge in the $i$-th query.


-----Output-----

Print $m$ integers — the answers to the queries. The $i$-th value should be equal to the number of pairs of vertices $(u, v)$ ($u < v$) such that the maximum weight of an edge on a simple path between $u$ and $v$ doesn't exceed $q_i$.

Queries are numbered from $1$ to $m$ in the order of the input.


-----Examples-----
Input
7 5
1 2 1
3 2 3
2 4 1
4 5 2
5 7 4
3 6 2
5 2 3 4 1

Output
21 7 15 21 3 

Input
1 2
1 2

Output
0 0 

Input
3 3
1 2 1
2 3 2
1 3 2

Output
1 3 3 



-----Note-----

The picture shows the tree from the first example: [Image]

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Sorting

Tree algorithms

Divide and conquer

Spanning trees
Skill types: Sorting

Starter code:

Solutions:
import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
par = [-1] * n

def c(x):
	return x * (x - 1) // 2

def find(x):
	if par[x] < 0:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def unite(x, y):
	x = find(x)
	y = find(y)
	if x == y:
		return False
	else:
		if par[x] > par[y]:
			(x, y) = (y, x)
		par[x] += par[y]
		par[y] = x
		return True

def same(x, y):
	return find(x) == find(y)

def size(x):
	return -par[find(x)]
import collections
Edge = collections.defaultdict(list)
for _ in range(n - 1):
	(u, v, w) = list(map(int, input().split()))
	Edge[w].append((u, v))
Q = [int(i) for i in input().split()]
q = max(Q)
Ans = [0] * (q + 1)
ans = 0
for i in range(1, q + 1):
	for (u, v) in Edge[i]:
		if same(u - 1, v - 1):
			continue
		else:
			(uu, vv) = (size(u - 1), size(v - 1))
			unite(u - 1, v - 1)
			uv = size(u - 1)
			ans += c(uv) - c(uu) - c(vv)
	Ans[i] = ans
Ans2 = []
for q in Q:
	Ans2.append(Ans[q])
print(*Ans2)


class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		self.parent[self.find(b)] = self.find(a)

def cntPairCombinations(size):
	if size <= 1:
		return 0
	else:
		return size * (size - 1) // 2

def main():
	(n, m) = readIntArr()
	wuv = []
	for _ in range(n - 1):
		(u, v, w) = readIntArr()
		u -= 1
		v -= 1
		wuv.append([w, u, v])
	wuv.sort()
	nodeUf = UnionFind(n)
	groupSize = [1] * n
	weights = []
	nPairs = []
	totalPairs = 0
	for i in range(n - 1):
		(w, u, v) = wuv[i]
		weights.append(w)
		sz1 = groupSize[nodeUf.find(u)]
		sz2 = groupSize[nodeUf.find(v)]
		subtract = cntPairCombinations(sz1) + cntPairCombinations(sz2)
		add = cntPairCombinations(sz1 + sz2)
		totalPairs += add - subtract
		nPairs.append(totalPairs)
		nodeUf.union(u, v)
		groupSize[nodeUf.find(u)] = sz1 + sz2
	allans = []
	qq = readIntArr()
	for q in qq:
		b = n - 1
		i = -1
		while b > 0:
			while i + b < n - 1 and weights[i + b] <= q:
				i += b
			b //= 2
		if i == -1:
			allans.append(0)
		else:
			allans.append(nPairs[i])
	oneLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import sys
input = sys.stdin.readline

class Node:

	def __init__(self):
		self.data = 0
		self.parent = None
		self.rank = 0
d = {}

def makeSet(data):
	node = Node()
	node.data = data
	node.parent = node
	d[data] = node

def get(val):
	return val * (val - 1) // 2

def union(data1, data2, ele, res):
	node1 = d[data1]
	node2 = d[data2]
	parent1 = find(node1)
	parent2 = find(node2)
	temp = res
	temp -= get(ele[parent1.data])
	temp -= get(ele[parent2.data])
	if parent1.rank >= parent2.rank:
		parent1.rank = parent1.rank + 1 if parent1.rank == parent2.rank else parent1.rank
		parent2.parent = parent1
		ele[parent1.data] += ele[parent2.data]
	else:
		parent1.parent = parent2
		ele[parent2.data] += ele[parent1.data]
	temp += get(ele[parent1.parent.data])
	return temp

def findData(data):
	return find(d[data]).data

def find(node):
	parent = node.parent
	if parent == node:
		return node
	node.parent = find(node.parent)
	return node.parent
(n, q) = map(int, input().split())
ar = []
for i in range(n - 1):
	(a, b, w) = map(int, input().split())
	ar.append((a, b, w))
qr = [int(x) for x in input().split()]
for i in range(q):
	qr[i] = (qr[i], i)
ar.sort(key=lambda x: x[2])
qr.sort(key=lambda x: x[0])
for i in range(1, n + 1):
	makeSet(i)
ele = [1] * (n + 1)
ans = []
res = 0
pos = 0
for i in range(q):
	while pos < n - 1 and ar[pos][2] <= qr[i][0]:
		res = union(ar[pos][0], ar[pos][1], ele, res)
		pos += 1
	ans.append((str(res), qr[i][1]))
ans.sort(key=lambda x: x[1])
r = []
for i in ans:
	r.append(i[0])
print(' '.join(r))


(n, m) = map(int, input().split())
dp = []
for i in range(n - 1):
	(u, v, w) = map(int, input().split())
	dp.append((w, u - 1, v - 1))
dp = sorted(dp)
q = [int(x) for x in input().split()]
pos = []
for i in range(m):
	pos.append(i)
Q = sorted(zip(q, pos))
par = []
for i in range(0, n):
	par.append(i)
rank = [1] * n

def find(x):
	if par[x] != x:
		par[x] = find(par[x])
	return par[x]
global res
res = 0

def union(x, y):
	global res
	X = find(x)
	Y = find(y)
	if rank[X] < rank[Y]:
		temp = X
		X = Y
		Y = temp
	res = res - rank[X] * (rank[X] - 1) // 2
	res = res - rank[Y] * (rank[Y] - 1) // 2
	rank[X] += rank[Y]
	res = res + rank[X] * (rank[X] - 1) // 2
	par[Y] = X
ans = [0] * m
ptr = 0
for i in range(0, m):
	while ptr < n - 1 and dp[ptr][0] <= Q[i][0]:
		a = dp[ptr][1]
		b = dp[ptr][2]
		union(a, b)
		ptr += 1
	ans[Q[i][1]] = res
print(*ans)


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
(N, M) = map(int, readline().split())
E = []
for i in range(N - 1):
	(u, v, w) = map(int, readline().split())
	E.append((w, u - 1, v - 1))
E.sort()
Q = set()
MP = defaultdict(list)
for (i, q) in enumerate(map(int, readline().split())):
	MP[q].append(i)
	Q.add(q)
Q = list(Q)
Q.sort()

def root(x):
	if x == p[x]:
		return x
	y = x
	while y != p[y]:
		y = p[y]
	while x != y:
		(p[x], x) = (y, p[x])
	return y
(*p,) = range(N)
sz = [1] * N
c = 0

def unite(x, y):
	global c
	px = root(x)
	py = root(y)
	if px == py:
		return 0
	c += sz[px] * sz[py]
	if sz[px] < sz[py]:
		p[py] = px
		sz[px] += sz[py]
	else:
		p[px] = py
		sz[py] += sz[px]
	return 1
k = 0
ans = [N * (N - 1) // 2] * M
L = len(Q)
for (w, u, v) in E:
	while k < L and Q[k] < w:
		e = Q[k]
		for i in MP[e]:
			ans[i] = c
		k += 1
	unite(u, v)
sys.stdout.write(' '.join(map(str, ans)))
sys.stdout.write('\n')


import sys
input = sys.stdin.readline
from collections import *

class Unionfind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [1] * n

	def root(self, x):
		r = x
		while not self.par[r] < 0:
			r = self.par[r]
		t = x
		while t != r:
			tmp = t
			t = self.par[t]
			self.par[tmp] = r
		return r

	def unite(self, x, y):
		rx = self.root(x)
		ry = self.root(y)
		if rx == ry:
			return
		if self.rank[rx] <= self.rank[ry]:
			self.par[ry] += self.par[rx]
			self.par[rx] = ry
			if self.rank[rx] == self.rank[ry]:
				self.rank[ry] += 1
		else:
			self.par[rx] += self.par[ry]
			self.par[ry] = rx

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def count(self, x):
		return -self.par[self.root(x)]
(n, m) = map(int, input().split())
edges = []
for _ in range(n - 1):
	(u, v, w) = map(int, input().split())
	edges.append((u - 1, v - 1, w))
edges.sort(key=lambda t: t[2])
uf = Unionfind(n)
cnt = [0] * (2 * 10 ** 5 + 100)
for (u, v, w) in edges:
	cnt[w] += uf.count(u) * uf.count(v)
	uf.unite(u, v)
acc = [0]
for cnt_i in cnt:
	acc.append(acc[-1] + cnt_i)
q = list(map(int, input().split()))
ans = []
for qi in q:
	ans.append(acc[qi + 1])
print(*ans)


import sys
from itertools import accumulate
from operator import itemgetter

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return list(map(int, input().split()))

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)
		self.size = [1] * (n + 1)
		self.tree = [True] * (n + 1)

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			self.tree[x] = False
			return
		if not self.tree[x] or not self.tree[y]:
			self.tree[x] = self.tree[y] = False
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
			self.size[y] += self.size[x]
		else:
			self.par[y] = x
			self.size[x] += self.size[y]
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def is_same(self, x, y):
		return self.find(x) == self.find(y)

	def get_size(self, x=None):
		if x is not None:
			return self.size[self.find(x)]
		else:
			res = set()
			for i in range(self.n + 1):
				res.add(self.find(i))
			return len(res) - 1

	def is_tree(self, x):
		return self.tree[self.find(x)]
(N, M) = MAP()
edges = []
for i in range(N - 1):
	(a, b, c) = MAP()
	a -= 1
	b -= 1
	edges.append((c, a, b))
if N == 1:
	LIST()
	ans = [0] * M
	print(*ans)
	return
MAX = 2 * 10 ** 5 + 7
edges.sort(key=itemgetter(0))
C = [0] * MAX
uf = UnionFind(N)
prevc = edges[0][0]
for (c, a, b) in edges:
	if prevc != c:
		C[c] = C[prevc]
	sz1 = uf.get_size(a)
	C[c] -= sz1 * (sz1 - 1) // 2
	sz2 = uf.get_size(b)
	C[c] -= sz2 * (sz2 - 1) // 2
	uf.union(a, b)
	sz = sz1 + sz2
	C[c] += sz * (sz - 1) // 2
	prevc = c
C = list(accumulate(C, max))
Q = LIST()
ans = [0] * M
for (i, q) in enumerate(Q):
	ans[i] = C[q]
print(*ans)


import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members
(n, m) = map(int, input().split())
edges = []
for _ in range(n - 1):
	(u, v, w) = map(int, input().split())
	edges.append([u - 1, v - 1, w])
edges.sort(key=lambda x: x[2])
ww = [edges[i][2] for i in range(n - 1)]
uf = UnionFind(n)
c = [0] * (n + 1)
for i in range(1, n):
	(u, v, w) = edges[i - 1]
	s1 = uf.size(u)
	s2 = uf.size(v)
	uf.union(u, v)
	c[i] = c[i - 1] - s1 * (s1 - 1) // 2 - s2 * (s2 - 1) // 2 + (s1 + s2) * (s1 + s2 - 1) // 2
q = list(map(int, input().split()))
ans = []
for lim in q:
	idx = bisect_right(ww, lim)
	ans.append(c[idx])
print(*ans)


from sys import stdin
from copy import deepcopy
from collections import deque, defaultdict

def find_parent(n):
	nonlocal parent
	node = n
	while parent[node] != node:
		node = parent[node]
	parent[n] = node
	return parent[n]

def combination(num):
	return num * (num - 1) // 2
(n, m) = list(map(int, stdin.readline().split()))
graph = defaultdict(list)
edges = []
for _ in range(n - 1):
	edges.append(list(map(int, stdin.readline().split())))
queries = list(map(int, stdin.readline().split()))
edges.sort(key=lambda x: x[2], reverse=True)
parent = dict()
count = dict()
for i in range(1, n + 1):
	parent[i] = i
	count[i] = 1
ans = [0] * 200001
while len(edges) > 0:
	(u, v, w) = edges.pop()
	if u > v:
		(u, v) = (v, u)
	pv = find_parent(v)
	pu = find_parent(u)
	ans[w] -= combination(count[pu]) + combination(count[pv])
	ans[w] += combination(count[pu] + count[pv])
	count[pu] += count[pv]
	count[pv] = 0
	parent[pv] = parent[pu]
for i in range(1, len(ans)):
	ans[i] = ans[i - 1] + ans[i]
for i in queries:
	print(ans[i], end=' ')


import heapq
import sys
input = sys.stdin.readline

def get_root(s):
	v = []
	while not s == root[s]:
		v.append(s)
		s = root[s]
	for i in v:
		root[i] = s
	return s

def unite(s, t):
	(rs, rt) = (get_root(s), get_root(t))
	if not rs ^ rt:
		return
	if rank[s] == rank[t]:
		rank[rs] += 1
	if rank[s] >= rank[t]:
		root[rt] = rs
		size[rs] += size[rt]
	else:
		root[rs] = rt
		size[rt] += size[rs]
	return

def get_size(s):
	return size[get_root(s)]

def same(s, t):
	return True if get_root(s) == get_root(t) else False
(n, m) = map(int, input().split())
h = []
for _ in range(n - 1):
	(u, v, w) = map(int, input().split())
	heapq.heappush(h, (w, u, v))
heapq.heappush(h, (1145141919, 810, 810))
q = list(map(int, input().split()))
p = []
for i in range(m):
	heapq.heappush(p, (q[i], i))
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
ans = [0] * m
now = 0
while p:
	(qi, i) = heapq.heappop(p)
	while h[0][0] <= qi:
		(w, u, v) = heapq.heappop(h)
		(su, sv) = (get_size(u), get_size(v))
		now -= su * (su - 1) // 2
		now -= sv * (sv - 1) // 2
		now += (su + sv) * (su + sv - 1) // 2
		unite(u, v)
	ans[i] = now
print(*ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

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

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

def solve():
	ans = 0

	class MergeFind:

		def __init__(self, n):
			self.parent = list(range(n))
			self.size = [1] * n
			self.num_sets = n
			self.lista = [[_] for _ in range(n)]

		def find(self, a):
			to_update = []
			while a != self.parent[a]:
				to_update.append(a)
				a = self.parent[a]
			for b in to_update:
				self.parent[b] = a
			return self.parent[a]

		def merge(self, a, b):
			a = self.find(a)
			b = self.find(b)
			if a == b:
				return
			if self.size[a] < self.size[b]:
				(a, b) = (b, a)
			self.num_sets -= 1
			self.parent[b] = a
			self.size[a] += self.size[b]
			self.lista[a] += self.lista[b]
			self.lista[b] = []

		def set_size(self, a):
			return self.size[self.find(a)]

		def __len__(self):
			return self.num_sets
	(n, q) = sep()
	edges = []
	for _ in range(n - 1):
		(a, b, w) = sep()
		a -= 1
		b -= 1
		edges.append((w, a, b))
	edges.sort()
	temp = lis()
	queries = []
	for i in range(q):
		queries.append((temp[i], i))
	queries.sort()
	pos = 0
	d = MergeFind(n)

	def f(i):
		return i * (i - 1) // 2
	answer = [0] * q
	for i in range(q):
		while pos < n - 1 and edges[pos][0] <= queries[i][0]:
			(a, b) = (edges[pos][1], edges[pos][2])
			A = d.find(a)
			B = d.find(b)
			ans -= f(d.size[A])
			ans -= f(d.size[B])
			d.merge(A, B)
			A = d.find(a)
			ans += f(d.size[A])
			pos += 1
		answer[queries[i][1]] = ans
	print(*answer)
solve()


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

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

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())
(n, m) = inpl()
edge = []
for _ in range(n - 1):
	(a, b, c) = inpl()
	edge.append((c, a - 1, b - 1))
edge.sort()
q = inpl()
d = defaultdict(list)
for (i, x) in enumerate(q):
	d[x].append(i)
uf = UnionFind(n)
ans = 0
ind = 0

def c2(x):
	return x * (x - 1) // 2
res = [-1] * m
for x in sorted(list(set(q))):
	while ind < n - 1 and edge[ind][0] <= x:
		(c, a, b) = edge[ind]
		if uf.same(a, b):
			continue
		sa = uf.size(a)
		sb = uf.size(b)
		ans -= c2(sa)
		ans -= c2(sb)
		uf.union(a, b)
		ans += c2(uf.size(a))
		ind += 1
	for i in d[x]:
		res[i] = ans
print(*res)


def find(u):
	if parent[u] == u:
		return u
	parent[u] = find(parent[u])
	return parent[u]

def union(a, b):
	u = parent[a]
	v = parent[b]
	p = size[u]
	q = size[v]
	if size[u] > size[v]:
		parent[v] = u
		size[u] += size[v]
	else:
		parent[u] = v
		size[v] += size[u]
	return p * q
(n, m) = map(int, input().split())
edges = []
for j in range(n - 1):
	(u, v, val) = map(int, input().split())
	edges.append([val, u, v])
edges.sort()
parent = [i for i in range(n + 1)]
size = [1 for i in range(n + 1)]
curr = 1
val = [0] * (2 * 10 ** 5 + 1)
ind = 0
while curr <= 2 * 10 ** 5:
	res = 0
	while ind < n - 1 and edges[ind][0] == curr:
		(u, v) = (edges[ind][1], edges[ind][2])
		if find(u) == find(v):
			pass
		else:
			res += union(u, v)
		ind += 1
	val[curr] = res + val[curr - 1]
	curr += 1
ans = []
b = list(map(int, input().split()))
for j in b:
	ans.append(val[j])
print(*ans)


import sys
sys.setrecursionlimit(10 ** 9)

def find(a):
	if par[a] == a:
		return a
	par[a] = find(par[a])
	return par[a]
(n, m) = map(int, input().split())
ed = []
par = [i for i in range(n)]
size = [1 for i in range(n)]
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	ed.append([a - 1, b - 1, c])
ed.sort(key=lambda x: x[2])
it = list(map(int, input().split()))
it = [[i, j, 0] for (j, i) in enumerate(it)]
it.sort()
ind = 0
tot = 0
j = 0
ss = {}
for i in it[:]:
	while ind < n - 1:
		if ed[ind][2] <= i[0]:
			a = find(ed[ind][0])
			b = find(ed[ind][1])
			if a != b:
				tot += size[a] * size[b]
				if size[a] >= size[b]:
					par[b] = a
					size[a] += size[b]
					size[b] = 0
				else:
					par[a] = b
					size[b] += size[a]
					size[a] = 0
			ind += 1
		else:
			break
	it[j][2] = tot
	j += 1
it.sort(key=lambda x: x[1])
aa = [i[2] for i in it]
print(*aa)


(n, m) = list(map(int, input().split()))
maxN = 2 * 10 ** 5 + 10
edges = [[] for i in range(0, maxN)]
que = [[] for _ in range(0, maxN)]
ans = [0] * m
sz = [1 for _ in range(0, n)]
p = [i for i in range(0, n)]
total_sum = 0

def get(u):
	if p[u] == u:
		return u
	p[u] = get(p[u])
	return p[u]

def unite(u, v):
	u = get(u)
	v = get(v)
	if u == v:
		return
	nonlocal total_sum
	total_sum -= sz[u] * (sz[u] - 1) // 2
	total_sum -= sz[v] * (sz[v] - 1) // 2
	total_sum += (sz[u] + sz[v]) * (sz[u] + sz[v] - 1) // 2
	if sz[u] < sz[v]:
		p[u] = v
		sz[v] += sz[u]
	else:
		p[v] = u
		sz[u] += sz[v]
for i in range(1, n):
	(u, v, w) = list(map(int, input().split()))
	u -= 1
	v -= 1
	edges[w].append((u, v))
ques = list(map(int, input().split()))
for i in range(0, m):
	que[ques[i]].append(i)
for i in range(0, maxN):
	for (u, v) in edges[i]:
		unite(u, v)
	for id in que[i]:
		ans[id] = total_sum
print(' '.join((str(x) for x in ans)))


(n, m) = [int(x) for x in input().split()]
link = [0] * (n + 1)
size = [0] * (n + 1)
arr = [0] * m
res = 0
for i in range(1, n + 1):
	link[i] = i
	size[i] = 1

def find(x):
	while x != link[x]:
		x = link[x]
	return x

def comb(n):
	return n * (n - 1) // 2

def unite(a, b, res):
	a = find(a)
	b = find(b)
	if size[a] < size[b]:
		(a, b) = (b, a)
	res = res - comb(size[a]) - comb(size[b]) + comb(size[a] + size[b])
	size[a] += size[b]
	link[b] = a
	return res
edges = []
ask = []
for i in range(n - 1):
	(x, y, z) = [int(x) for x in input().split()]
	edges.append((z, x, y))
edges.sort()
x = 0
edges.append((10 ** 100, 1, 1))
ask = sorted(zip([int(x) for x in input().split()], list(range(m))))
for i in range(m):
	while edges[x][0] <= ask[i][0]:
		res = unite(edges[x][1], edges[x][2], res)
		x += 1
	arr[ask[i][1]] = res
print(*arr)


from sys import stdin, stdout

class Dsu:

	def __init__(self, n):
		self.dsu = [i for i in range(n + 1)]
		self.sz = [1 for _ in range(n + 1)]

	def __get__(self, x):
		if x == self.dsu[x]:
			return x
		self.dsu[x] = self.__get__(self.dsu[x])
		return self.dsu[x]

	def join(self, x, y):
		x = self.__get__(x)
		y = self.__get__(y)
		if x == y:
			return 0
		if self.sz[x] < self.sz[y]:
			(x, y) = (y, x)
		ret = self.sz[x] * self.sz[y]
		self.sz[x] += self.sz[y]
		self.dsu[y] = x
		return ret
(n, m) = map(int, stdin.readline().split())
dsu = Dsu(n)
edges = [list(map(int, stdin.readline().split())) for i in range(n - 1)]
queries = [(int(x), i) for (i, x) in enumerate(stdin.readline().split())]
edges.sort(key=lambda x: x[2])
queries.sort(key=lambda x: x[0])
index = 0
answer = [0 for i in range(m)]
total = 0
for (q, i) in queries:
	while index < len(edges) and edges[index][2] <= q:
		total += dsu.join(edges[index][0], edges[index][1])
		index += 1
	answer[i] = total
for x in answer:
	stdout.write(str(x) + ' ')


import os
import sys
from io import BytesIO, IOBase

def find(p, z):
	a = []
	while p[z] != z:
		a.append(z)
		z = p[z]
	for i in a:
		p[i] = z
	return z

def com(x):
	return x * (x - 1) // 2

def main():
	(n, m) = map(int, input().split())
	a = [tuple(map(int, input().split())) for _ in range(n - 1)]
	a.sort(key=lambda x: x[2])
	q = sorted(zip(map(int, input().split()), list(range(m))), key=lambda x: x[0])
	(ans, j, z) = ([0] * m, 0, 0)
	p = [i for i in range(n + 1)]
	s = [1 for _ in range(n + 1)]
	for i in q:
		while j < n - 1 and a[j][2] <= i[0]:
			(x, y) = (find(p, a[j][0]), find(p, a[j][1]))
			if x != y:
				z += com(s[x] + s[y]) - com(s[x]) - com(s[y])
				if s[x] >= s[y]:
					s[x] += s[y]
					p[y] = p[x]
				else:
					s[y] += s[x]
					p[x] = p[y]
			j += 1
		ans[i[1]] = z
	print(*ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
from sys import stdin, stdout
from collections import defaultdict
from collections import deque
import math
import copy
(N, E) = [int(x) for x in stdin.readline().split()]
s = 0
size = [1] * N
f = [x for x in range(N)]

def getf(v):
	stack = []
	while f[v] != v:
		stack.append(v)
		v = f[v]
	for idx in stack:
		f[idx] = v
	return v

def merge(f, v, u):
	global s
	t1 = getf(v)
	t2 = getf(u)
	if t1 != t2:
		A = size[t1]
		B = size[t2]
		s -= A * (A - 1) // 2
		s -= B * (B - 1) // 2
		size[t1] = size[t1] + size[t2]
		C = size[t1]
		s += C * (C - 1) // 2
		f[t2] = t1
w_edge = {}
for i in range(N - 1):
	(u, v, w) = [int(x) for x in stdin.readline().split()]
	if u > v:
		(u, v) = (v, u)
	if w not in w_edge:
		w_edge[w] = []
	w_edge[w].append((u, v))
q = [0] * 200000
for i in range(200000):
	if i + 1 in w_edge:
		for e in w_edge[i + 1]:
			(u, v) = e
			merge(f, u - 1, v - 1)
		q[i] = s
	elif i != 0:
		q[i] = q[i - 1]
	else:
		q[i] = 0
arr = [int(x) for x in stdin.readline().split()]
ans = [0] * E
for i in range(E):
	ans[i] = q[arr[i] - 1]
print(*ans)


def find_ancestor(i, father):
	if father[i] == i:
		return i
	father[i] = find_ancestor(father[i], father)
	return father[i]

def connect(i, j, father, n_child):
	i_anc = find_ancestor(i, father)
	j_anc = find_ancestor(j, father)
	if n_child[i_anc] > n_child[j_anc]:
		n_child[i_anc] += n_child[j_anc]
		father[j_anc] = i_anc
	else:
		n_child[j_anc] += n_child[i_anc]
		father[i_anc] = j_anc
(n, m) = map(int, input().split())
edges = []
father = [i for i in range(n)]
n_child = [1] * n
for i in range(n - 1):
	(i, j, w) = map(int, input().split())
	edges.append((i - 1, j - 1, w))
edges.sort(key=lambda x: -x[2])
queries = list(map(int, input().split()))
s_queries = sorted(queries)
ans = {}
w_limit = []
ans_cum = 0
for query in s_queries:
	while len(edges) and edges[-1][2] <= query:
		(i, j, w) = edges[-1]
		edges.pop()
		i_anc = find_ancestor(i, father)
		j_anc = find_ancestor(j, father)
		ans_cum += n_child[i_anc] * n_child[j_anc]
		connect(i, j, father, n_child)
	ans[query] = ans_cum
print(' '.join(list(map(str, [ans[query] for query in queries]))))


from sys import setrecursionlimit as SRL, stdin
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
fa = [i for i in range(200005)]
s = [1] * 200005

def find(x):
	t = []
	while fa[x] != x:
		t.append(x)
		x = fa[x]
	for i in t:
		fa[i] = x
	return fa[x]
ans = [0] * 200005
(n, q) = rrd()
w = []
for i in range(n - 1):
	(x, y, z) = rrd()
	w.append([z, x, y])
w.sort(key=lambda x: x[0])
for x in w:
	u = find(x[1])
	v = find(x[2])
	ans[x[0]] += s[u] * s[v]
	fa[u] = v
	s[v] += s[u]
for i in range(1, 200001):
	ans[i] += ans[i - 1]
q = list(rrd())
for x in q:
	print(ans[x], end=' ')


(n, m) = map(int, input().split())
edges = []
dsu = [i for i in range(n + 1)]
ans = [0 for i in range(2 * 10 ** 5 + 1)]
gang_num = [1 for i in range(n + 1)]
for i in range(n - 1):
	(u, v, w) = map(int, input().split())
	edges.append((w, u, v))
edges.sort()

def cal_num(n):
	return n * (n - 1) // 2

def union(u, v):
	(first, second) = (find(u), find(v))
	if first == second:
		return (0, 0, 0)
	dsu[first] = second
	(prev_f, prev_s) = (gang_num[first], gang_num[second])
	gang_num[second] += gang_num[first]
	return (gang_num[second], prev_f, prev_s)

def find(u):
	to_find = u
	while u != dsu[u]:
		u = dsu[u]
	dsu[to_find] = u
	return u
prev = 0
for each_edge in edges:
	(w, u, v) = each_edge
	(big, smallf, smalls) = union(u, v)
	ans[w] = prev + cal_num(big) - cal_num(smallf) - cal_num(smalls)
	prev = ans[w]
for i in range(1, len(ans)):
	if ans[i] == 0:
		ans[i] = ans[i - 1]
query = [int(i) for i in input().split()]
print(' '.join((str(ans[i]) for i in query)))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
g = {}

def dfs(v, p=-1):
	c = [dfs(child, v) for child in g.get(v, set()) - {p}]
	c.sort(key=len, reverse=True)
	r = []
	i = 0
	while c:
		if i >= len(c[-1]):
			c.pop()
		else:
			o = max(i, k - i - 1)
			s = q = 0
			for x in c:
				if len(x) <= o:
					q = max(q, x[i])
				else:
					s += x[o]
					q = max(q, x[i] - x[o])
			r.append(q + s)
			i += 1
	r.append(0)
	for i in range(len(r) - 1, 0, -1):
		r[i - 1] = max(r[i - 1], r[i])
	while len(r) > 1 and r[-2] == 0:
		r.pop()
	o = (r[k] if k < len(r) else 0) + a[v]
	r.insert(0, max(o, r[0]))
	return r
for _ in range(1, n):
	(u, v) = map(lambda x: int(x) - 1, input().split())
	g.setdefault(u, set()).add(v)
	g.setdefault(v, set()).add(u)
print(dfs(0)[0])


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rnk = [0] * (n + 1)

	def Find_Root(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.Find_Root(self.root[x])
			return self.root[x]

	def Unite(self, x, y):
		x = self.Find_Root(x)
		y = self.Find_Root(y)
		if x == y:
			return
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.Find_Root(x) == self.Find_Root(y)

	def Count(self, x):
		return -self.root[self.Find_Root(x)]
import sys
input = sys.stdin.readline
from bisect import bisect_right
(N, M) = map(int, input().split())
uni = UnionFind(N + 1)
Edges = {}
for _ in range(N - 1):
	(a, b, w) = map(int, input().split())
	if not w in Edges:
		Edges[w] = [(a, b)]
	else:
		Edges[w].append((a, b))
Query = list(map(int, input().split()))
Weights = sorted(list(Edges.keys()))
Score = [0]
score = 0
for w in Weights:
	for (a, b) in Edges[w]:
		c1 = uni.Count(a)
		c2 = uni.Count(b)
		c = c1 + c2
		score += c * (c - 1) // 2 - c1 * (c1 - 1) // 2 - c2 * (c2 - 1) // 2
		uni.Unite(a, b)
	Score.append(score)
ans = []
for q in Query:
	ind = bisect_right(Weights, q)
	ans.append(Score[ind])
print(*ans)


from collections import Counter

def find(p, parent):
	if p == parent[p]:
		return p
	parent[p] = find(parent[p], parent)
	return parent[p]

def calc(i):
	return i * (i - 1) // 2

def union(x, y, parent, rank, size):
	u = find(x, parent)
	v = find(y, parent)
	if u == v:
		return 0
	if rank[u] > rank[v]:
		(u, v) = (v, u)
	parent[u] = v
	size[v] += size[u]
	if rank[u] == rank[v]:
		rank[v] += 1
	return size[v]

def count(i, parent, size):
	return size[find(i, parent)]

def solve():
	(n, m) = map(int, input().split())
	e = []
	parent = {i: i for i in range(1, n + 1)}
	rank = {i: 0 for i in range(1, n + 1)}
	size = {i: 1 for i in range(1, n + 1)}
	for _ in range(n - 1):
		(x, y, w) = map(int, input().split())
		e.append((w, (x, y)))
	e.sort()
	l = list(map(int, input().split()))
	a = [i for i in l]
	a.sort()
	j = 0
	ans = {}
	x = 0
	for i in a:
		while j < n - 1 and e[j][0] <= i:
			u = count(e[j][1][0], parent, size)
			v = count(e[j][1][1], parent, size)
			w = union(e[j][1][0], e[j][1][1], parent, rank, size)
			j += 1
			x += calc(w) - calc(u) - calc(v)
		ans[i] = x
	z = []
	for i in l:
		z.append(ans[i])
	print(*z)
solve()


import typing
from bisect import bisect_right, bisect_left
import sys

def input():
	return sys.stdin.readline().rstrip()

class DSU:

	def __init__(self, n: int=0) -> None:
		self._n = n
		self.parent_or_size = [-1] * n

	def merge(self, a: int, b: int) -> int:
		assert 0 <= a < self._n
		assert 0 <= b < self._n
		x = self.leader(a)
		y = self.leader(b)
		if x == y:
			return x
		if -self.parent_or_size[x] < -self.parent_or_size[y]:
			(x, y) = (y, x)
		self.parent_or_size[x] += self.parent_or_size[y]
		self.parent_or_size[y] = x
		return x

	def same(self, a: int, b: int) -> bool:
		assert 0 <= a < self._n
		assert 0 <= b < self._n
		return self.leader(a) == self.leader(b)

	def leader(self, a: int) -> int:
		assert 0 <= a < self._n
		parent = self.parent_or_size[a]
		while parent >= 0:
			if self.parent_or_size[parent] < 0:
				return parent
			(self.parent_or_size[a], a, parent) = (self.parent_or_size[parent], self.parent_or_size[parent], self.parent_or_size[self.parent_or_size[parent]])
		return a

	def size(self, a: int) -> int:
		assert 0 <= a < self._n
		return -self.parent_or_size[self.leader(a)]

	def groups(self) -> typing.List[typing.List[int]]:
		leader_buf = [self.leader(i) for i in range(self._n)]
		result: typing.List[typing.List[int]] = [[] for _ in range(self._n)]
		for i in range(self._n):
			result[leader_buf[i]].append(i)
		return list(filter(lambda r: r, result))

def slv():
	(n, m) = map(int, input().split())
	dsu = DSU(n + 100)
	edge = []
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		edge.append((u, v, w))
	query = list(map(int, input().split()))
	edge.sort(key=lambda x: x[2])
	tot = 0
	costdata = [0]
	weightdata = [0]
	for (u, v, w) in edge:
		tot += dsu.size(u) * dsu.size(v)
		dsu.merge(u, v)
		costdata.append(tot)
		weightdata.append(w)
	ans = []
	for q in query:
		cnt = bisect_right(weightdata, q) - 1
		ans.append(costdata[cnt])
	print(*ans)
	return

def main():
	t = 1
	for i in range(t):
		slv()
	return
main()


import sys
input = sys.stdin.readline

def nc2(val):
	return val * (val - 1) // 2

def find(a, par):
	p = []
	while a != par[a]:
		p.append(a)
		a = par[a]
	for i in p:
		par[i] = a
	return a

def union(a, b, par, rank, val, tval):
	if rank[a] < rank[b]:
		par[a] = b
		val[b] = tval
	elif rank[b] > rank[a]:
		par[b] = a
		val[a] = tval
	else:
		par[a] = b
		val[b] = tval
		rank[a] = rank[a] + 1
(n, m) = map(int, input().split())
A = []
for i in range(n - 1):
	(u, v, w) = map(int, input().split())
	A.append([u, v, w])
A.sort(key=lambda x: x[2])
par = [i for i in range(n + 1)]
rank = [0 for i in range(n + 1)]
val = [1 for i in range(n + 1)]
w = [0 for i in range(2 * 10 ** 5 + 1)]
tval = 0
for i in range(n - 1):
	(a, b) = (find(A[i][0], par), find(A[i][1], par))
	if a != b:
		(x, y) = (val[a], val[b])
		tval = tval + (nc2(x + y) - nc2(x) - nc2(y))
		union(a, b, par, rank, val, x + y)
	w[A[i][2]] = tval
v = 0
for i in range(2 * 10 ** 5 + 1):
	if w[i] != 0:
		v = w[i]
	w[i] = v
C = list(map(int, input().split()))
for i in range(m):
	print(w[C[i]], end=' ')
print()


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

def main():
	(n, m) = map(int, input().split())
	l = []
	for i in range(n - 1):
		(a1, b, c) = map(int, input().split())
		l.append((c, a1, b))
	a = list(map(int, input().split()))
	e = a + []
	l.sort()
	a.sort()
	p = [i for i in range(n + 1)]
	size = [1 for i in range(n + 1)]

	def get(a1):
		if p[a1] != a1:
			p[a1] = get(p[a1])
		return p[a1]

	def union(a1, b):
		a1 = get(a1)
		b = get(b)
		if size[a1] < size[b]:
			(a1, b) = (b, a1)
		p[a1] = b
		size[b] += size[a1]
	t = 0
	ans = 0
	de = defaultdict(int)
	for i in a:
		de[i] = n * (n - 1) // 2
	i = 0
	while i < n - 1:
		if l[i][0] <= a[t]:
			if get(l[i][1]) != get(l[i][2]):
				c = size[get(l[i][2])]
				d = size[get(l[i][1])]
				ans += (c + d) * (c + d - 1) // 2 - c * (c - 1) // 2 - d * (d - 1) // 2
				union(l[i][1], l[i][2])
				i += 1
		else:
			de[a[t]] = ans
			t += 1
			if t == n:
				break
	for i in e:
		print(de[i], end=' ')
t = threading.Thread(target=main)
t.start()
t.join()


class UnionFind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [0] * n

	def Find(self, x):
		if self.par[x] < 0:
			return x
		else:
			self.par[x] = self.Find(self.par[x])
			return self.par[x]

	def Unite(self, x, y):
		x = self.Find(x)
		y = self.Find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[y] += self.par[x]
				self.par[x] = y
			else:
				self.par[x] += self.par[y]
				self.par[y] = x
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

	def Same(self, x, y):
		return self.Find(x) == self.Find(y)

	def Size(self, x):
		return -self.par[self.Find(x)]
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
X = []
edge = []
for i in range(n - 1):
	(u, v, w) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	X.append((w, 0, i))
	edge.append((u, v))
Q = list(map(int, input().split()))
for (i, q) in enumerate(Q):
	X.append((q, 1, i))
X.sort(key=lambda x: (x[0], x[1]))
uf = UnionFind(n)
ans = [0] * m
total = 0
for (w, t, i) in X:
	if t == 0:
		(u, v) = edge[i]
		su = uf.Size(u)
		sv = uf.Size(v)
		total += su * sv
		uf.Unite(u, v)
	else:
		ans[i] = total
print(*ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_left as bsl
(n, m) = map(int, input().split())
graph = [set([]) for s in range(n)]
weight = []
for s in range(n - 1):
	(a, b, w) = map(int, input().split())
	a -= 1
	b -= 1
	weight.append((w, (min(a, b), max(a, b))))
	graph[a].add(b)
	graph[b].add(a)
weight.sort(key=lambda x: x[0])
group = list(range(n))
count = {}

def find(node):
	comp = []
	while group[node] != node:
		comp.append(node)
		node = group[node]
	for i in comp:
		group[i] = node
	return group[node]
ans = []
cumans = 0
for s in range(n - 1):
	w = weight[s][0]
	edge = weight[s][1]
	group1 = find(edge[0])
	group2 = find(edge[1])
	if not group1 in count:
		count[group1] = 1
	if not group2 in count:
		count[group2] = 1
	cumans -= count[group1] * (count[group1] - 1) // 2
	cumans -= count[group2] * (count[group2] - 1) // 2
	if count[group1] <= count[group2]:
		count[group2] += count[group1]
		count.pop(group1)
		cumans += count[group2] * (count[group2] - 1) // 2
		group[group1] = group2
	else:
		count[group1] += count[group2]
		count.pop(group2)
		cumans += count[group1] * (count[group1] - 1) // 2
		group[group2] = group1
	if s > 0 and weight[s - 1][0] == weight[s][0]:
		ans[-1] = cumans
	else:
		ans.append(cumans)
queries = list(map(int, input().split()))
weights = list(set([x[0] for x in weight]))
weights.sort()
if len(weights) == 0:
	print(*[0 for s in range(m)])
else:
	out = []
	for s in range(m):
		w = queries[s]
		ind = min(bsl(weights, w), len(weights) - 1)
		if weights[ind] > w:
			ind -= 1
		if ind == -1:
			out.append(0)
		else:
			out.append(ans[ind])
	print(*out)


from operator import itemgetter
import sys
input = sys.stdin.readline

class UnionFind:

	def __init__(self, n):
		self.parent = [-1] * n
		self.cnt = n

	def root(self, x):
		if self.parent[x] < 0:
			return x
		else:
			self.parent[x] = self.root(self.parent[x])
			return self.parent[x]

	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x != y:
			if self.parent[x] > self.parent[y]:
				(x, y) = (y, x)
			self.parent[x] += self.parent[y]
			self.parent[y] = x
			self.cnt -= 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def get_size(self, x):
		return -self.parent[self.root(x)]

	def get_cnt(self):
		return self.cnt
(n, m) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n - 1)]
q = list(map(int, input().split()))
info = sorted(info, key=itemgetter(2))
ans = [0] * (2 * 10 ** 5)
uf = UnionFind(2 * 10 ** 5)
info_i = 0
for i in range(2 * 10 ** 5):
	if i - 1 >= 0:
		ans[i] = ans[i - 1]
	while True:
		if info_i >= n - 1:
			break
		if info[info_i][2] == i + 1:
			(a, b, _) = info[info_i]
			a -= 1
			b -= 1
			num_a = uf.get_size(a)
			num_b = uf.get_size(b)
			num_ab = num_a + num_b
			comb_num_a = num_a * (num_a - 1) // 2
			comb_num_b = num_b * (num_b - 1) // 2
			comb_num_ab = num_ab * (num_ab - 1) // 2
			ans[i] += comb_num_ab - (comb_num_a + comb_num_b)
			uf.merge(a, b)
			info_i += 1
		else:
			break
res = [0] * len(q)
for (i, j) in enumerate(q):
	res[i] = ans[j - 1]
print(*res)


(n, m) = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(n - 1)]
queries = list(map(int, input().split()))
edges.sort(key=lambda x: x[2])
p = [i for i in range(n + 1)]
sz = [1] * (n + 1)
r = [1] * (n + 1)
ans = [0] * 200005

def get(u):
	if p[u] == u:
		return u
	p[u] = get(p[u])
	return p[u]

def join(u, v):
	u = get(u)
	v = get(v)
	if u != v:
		if r[u] < r[v]:
			(u, v) = (v, u)
		if r[u] == r[v]:
			r[u] = r[u] + 1
		p[v] = u
		temp = sz[u] * sz[v]
		sz[u] += sz[v]
		return temp
	return 0
for e in edges:
	ans[e[2]] += join(e[0], e[1])
for i in range(1, 200005):
	ans[i] += ans[i - 1]
for q in queries:
	print(ans[q], end=' ')


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
g = [[] for i in range(n)]
for i in range(n - 1):
	(v, u) = map(int, input().split())
	v -= 1
	u -= 1
	g[v].append(u)
	g[u].append(v)
dp = [[] for i in range(n)]
d = [1 for i in range(n)]

def dfs(v, p=-1):
	dp[v].append(a[v])
	for u in g[v]:
		if u == p:
			continue
		dfs(u, v)
		tmp = [-10 ** 18 for i in range(max(d[v], d[u] + 1))]
		for i in range(d[v]):
			for j in range(max(0, k - i), d[u]):
				tmp[min(i, j + 1)] = max(tmp[min(i, j + 1)], dp[v][i] + dp[u][j])
		for i in range(d[u]):
			tmp[i + 1] = max(tmp[i + 1], dp[u][i])
		for i in range(d[v]):
			dp[v][i] = max(dp[v][i], tmp[i])
		dp[v] += tmp[d[v]:]
		d[v] = max(d[v], d[u] + 1)
		for i in range(d[v] - 1, 0, -1):
			dp[v][i - 1] = max(dp[v][i - 1], dp[v][i])
dfs(0)
print(max(dp[0]))


from bisect import bisect
from math import inf

def union_init(s):
	d = [i for i in range(s)]
	size = [1 for i in range(s)]
	return (d, size)

def union_query(d, size, n):
	if d[n] != n:
		d[n] = union_query(d, size, d[n])
	return d[n]

def union_merge(d, size, x, y):
	xRoot = union_query(d, size, x)
	yRoot = union_query(d, size, y)
	if xRoot == yRoot:
		return
	if size[xRoot] < size[yRoot]:
		(xRoot, yRoot) = (yRoot, xRoot)
	d[yRoot] = xRoot
	size[xRoot] = size[xRoot] + size[yRoot]

def sizeComponent(d, size, x):
	root = union_query(d, size, x)
	return size[root]
nm = input().split()
n = int(nm[0])
m = int(nm[1])
(d, size) = union_init(n)
pairs = [(0, 0)]
edges = []
for _ in range(n - 1):
	edge = input().split()
	u = int(edge[0]) - 1
	v = int(edge[1]) - 1
	w = int(edge[2])
	edges.append((w, u, v))
edges.sort()
totalP = 0
for e in edges:
	u = e[1]
	v = e[2]
	uSize = sizeComponent(d, size, u)
	vSize = sizeComponent(d, size, v)
	totalP += uSize * vSize
	union_merge(d, size, u, v)
	pairs.append((e[0], totalP))
ms = [int(mi) for mi in input().split()]
answer = [0] * m
for (i, mi) in enumerate(ms):
	start = bisect(pairs, (mi, inf)) - 1
	answer[i] = pairs[start][1]
print(*answer)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
edges = []
for _ in range(n - 1):
	(i, j, w) = map(int, input().split())
	edges.append((i - 1, j - 1, w))
edges.sort(key=lambda e: e[-1])
Q = list(map(int, input().split()))
ans = [-1] * m
I = sorted(list(range(m)), key=lambda i: Q[i])
UF = [x for x in range(n)]
sz = [1] * n

def find(i):
	if UF[i] != i:
		UF[i] = find(UF[i])
	return UF[i]
cur = 0

def union(i, j):
	global cur
	pi = find(i)
	pj = find(j)
	x = sz[pi]
	y = sz[pj]
	cur -= x * (x - 1) // 2 + y * (y - 1) // 2
	cur += (x + y) * (x + y - 1) // 2
	if x >= y:
		sz[pi] += sz[pj]
		UF[pj] = pi
	else:
		sz[pj] += sz[pi]
		UF[pi] = pj
k = 0
for idx in I:
	while k < n - 1 and edges[k][-1] <= Q[idx]:
		(i, j, w) = edges[k]
		k += 1
		union(i, j)
	ans[idx] = cur
print(*ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt, log2
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

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

def modInverse(b):
	g = gcd(b, mod)
	if g != 1:
		return -1
	else:
		return pow(b, mod - 2, mod)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = inf

def bucketsort(order, seq):
	buckets = [0] * (max(seq) + 1)
	for x in seq:
		buckets[x] += 1
	for i in range(len(buckets) - 1):
		buckets[i + 1] += buckets[i]
	new_order = [-1] * len(seq)
	for i in reversed(order):
		x = seq[i]
		idx = buckets[x] = buckets[x] - 1
		new_order[idx] = i
	return new_order

def ordersort(order, seq, reverse=False):
	bit = max(seq).bit_length() >> 1
	mask = (1 << bit) - 1
	order = bucketsort(order, [x & mask for x in seq])
	order = bucketsort(order, [x >> bit for x in seq])
	if reverse:
		order.reverse()
	return order

def long_ordersort(order, seq):
	order = ordersort(order, [int(i & 2147483647) for i in seq])
	return ordersort(order, [int(i >> 31) for i in seq])

def multikey_ordersort(order, *seqs, sort=ordersort):
	for i in reversed(range(len(seqs))):
		order = sort(order, seqs[i])
	return order

class DisjointSetUnion:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		if a != b:
			if self.size[a] < self.size[b]:
				(a, b) = (b, a)
			self.num_sets -= 1
			self.parent[b] = a
			self.size[a] += self.size[b]

	def get_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def do(a):
	return a * (a - 1) // 2

def solve(case):
	(n, m) = sep()
	w = []
	u = []
	v = []
	if n == 1:
		ans = [0] * m
		print(' '.join((str(i) for i in ans)))
		return
	for i in range(n - 1):
		(l, r, ww) = sep()
		u.append(l)
		v.append(r)
		w.append(ww)
	q = lis()
	ind = [i for i in range(n)]
	order = multikey_ordersort(range(n - 1), w, u, v)
	order2 = multikey_ordersort(range(m), q)
	queries = []
	for i in order2:
		queries.append((q[i], ind[i]))
	curr = 0
	ans = [0] * m
	dsu = DisjointSetUnion(n + 1)
	ind = 0
	for i in order:
		while ind < m and w[i] > queries[ind][0]:
			ans[queries[ind][1]] = curr
			ind += 1
		curr -= do(dsu.get_size(u[i]))
		curr -= do(dsu.get_size(v[i]))
		dsu.union(u[i], v[i])
		curr += do(dsu.get_size(u[i]))
	while ind < m and inf > queries[ind][0]:
		ans[queries[ind][1]] = curr
		ind += 1
	print(' '.join((str(i) for i in ans)))
testcase(1)