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: introductory

Starter code:

Solutions:
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))







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)


'''input
3 3
1 2 1
2 3 2
1 3 2
'''
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

# main starts
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]
		
	# print(u, v, w)
	# print('parent', parent)
	# print('count', count)
	# print(ans)


for i in range(1, len(ans)):
	ans[i] = ans[i - 1] + ans[i]
# print(ans[:10])

for i in queries:
	print(ans[i], end = ' ')





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)



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)



# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
import sys
from sys import stdin, stdout
from collections import defaultdict
from collections import deque
import math
import copy

#T = int(input())
#N = int(input())
#s1 = input()
#s2 = input()
N,E = [int(x) for x in stdin.readline().split()]
#arr = [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):
    nonlocal 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
    else:
        if 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)


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):
    nonlocal 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")

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 fact(N):
    return N*fact(N-1) % 100 if N > 1 else 1
fact(2000)

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):
    nonlocal 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")

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 fact(N):
    return N*fact(N-1) % 100 if N > 1 else 1
fact(2100)

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):
    nonlocal 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")

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 fact(N):
    return N*fact(N-1) % 100 if N > 1 else 1
fact(2500)

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):
    nonlocal 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")

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 fact(N):
    return N*fact(N-1) % 100 if N > 1 else 1
fact(2800)

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):
    nonlocal 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")

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 fact(N):
    return N*fact(N-1) % 100 if N > 1 else 1
fact(2900)

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):
    nonlocal 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")

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline
N, M = list(map(int, readline().split()))
E = []
for i in range(N-1):
    u, v, w = list(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 fact(N):
    return N*fact(N-1) % 100 if N > 1 else 1
fact(3000)

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, = list(range(N))
sz = [1]*N
c = 0
def unite(x, y):
    nonlocal 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")


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 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=' ')


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=list(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=list(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
#print(it)
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]
              #  print(a,b,j,tot)
                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
    #ss[it[j][1]]=tot
    j+=1

it.sort(key=lambda x:x[1])
aa=[i[2] for i in it]

#for i in range(len(it)):
 #   print(ss[i],end=" ")
print(*aa)
        
    
    
        
    


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)

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 = list(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 = list(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)

# final map the index to the query
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)
        # it's tree father may not be same
        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]))))


# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

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

edges.sort()
A = [0] * (2*10**5+7)
uf = UnionFind(N)
prevc = edges[0][0]
for c, a, b in edges:
    if prevc != c:
        A[c] = A[prevc]
    sz1 = uf.get_size(a)
    A[c] -= sz1 * (sz1-1) // 2
    sz2 = uf.get_size(b)
    A[c] -= sz2 * (sz2-1) // 2
    uf.union(a, b)
    sz = sz1 + sz2
    A[c] += sz * (sz-1) // 2
    prevc = c

A = list(accumulate(A, max))
Q = LIST()
ans = [0] * M
for i, q in enumerate(Q):
    ans[i] = A[q]
print(*ans)


# -*- coding: utf-8 -*-

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)


# -*- coding: utf-8 -*-

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):
        t = []
        while self.par[x] != x:
            t.append(x)
            x = self.par[x]
        for i in t:
            self.par[i] = x
        return self.par[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)


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)