Victoria has a tree, $\mathbf{T}$, consisting of $N$ nodes numbered from $1$ to $N$. Each edge from node $U_i$ to $V_i$ in tree $\mathbf{T}$ has an integer weight, $W_i$.

Let's define the cost, $\mbox{C}$, of a path from some node $\mbox{X}$ to some other node $\mathbf{Y}$ as the maximum weight ($\mbox{w}$) for any edge in the unique path from node $\mbox{X}$ to node $\mathbf{Y}$.

Victoria wants your help processing $Q$ queries on tree $\mathbf{T}$, where each query contains $2$ integers, $\boldsymbol{\mbox{L}}$ and $\mbox{R}$, such that $L\leq R$. For each query, she wants to print the number of different paths in $\mathbf{T}$ that have a cost, $\mbox{C}$, in the inclusive range $[L,R]$.

It should be noted that path from some node $\mbox{X}$ to some other node $\mathbf{Y}$ is considered same as path from node $\mathbf{Y}$ to $\mbox{X}$ i.e $\{X,Y\}$ is same as $\{Y,X\}$. 

Input Format

The first line contains $2$ space-separated integers, $N$ (the number of nodes) and $Q$ (the number of queries), respectively. 

Each of the $N-1$ subsequent lines contain $3$ space-separated integers, $\mbox{U}$, $\mbox{V}$, and $\mbox{w}$, respectively, describing a bidirectional road between nodes $\mbox{U}$ and $\mbox{V}$ which has weight $\mbox{w}$. 

The $Q$ subsequent lines each contain $2$ space-separated integers denoting $\boldsymbol{\mbox{L}}$ and $\mbox{R}$.

Constraints

$1\leq N,Q\leq10^5$   
$1\leq U,V\leq N$   
$1\leq W\leq10^9$  
$1\leq L\leq R\leq10^9$ 

Scoring

$1\leq N,Q\leq10^3$ for $30\%$ of the test data.  
$1\leq N,Q\leq10^5$ for $\textbf{100\%}$ of the test data.

Output Format

For each of the $Q$ queries, print the number of paths in $\mathbf{T}$ having cost $\mbox{C}$ in the inclusive range $[L,R]$ on a new line.

Sample Input
5 5
1 2 3
1 4 2
2 5 6
3 4 1
1 1
1 2
2 3
2 5
1 6

Sample Output
1
3
5
5
10

Explanation

$Q_1$: $\{3,4\}$ 

$Q_2$: $\{1,3\},\{3,4\},\{1,4\}$ 

$Q_3$: $\{1,4\},\{1,2\},\{2,4\},\{1,3\},\{2,3\}$ 

$Q_4$: $\{1,4\},\{1,2\},\{2,4\},\{1,3\},\{2,3\}$ 

...etc.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Spanning trees


Solutions:
from collections import defaultdict
(N, Q) = map(int, input().split())
weights = []
for _ in range(N - 1):
	(U, V, W) = map(int, input().split())
	weights.append([W, U, V])
weights.sort()

class Node:

	def __init__(self, size, parent=None):
		self.size = size
		self.parent = parent
clusters = {n: Node(1) for n in range(1, N + 1)}
counts = defaultdict(int)
for (W, U, V) in weights:
	u = clusters[U]
	v = clusters[V]
	while u.parent:
		u = u.parent
	while v.parent:
		v = v.parent
	counts[W] += u.size * v.size
	n = Node(u.size + v.size)
	u.parent = n
	v.parent = n
	clusters[U] = n
	clusters[V] = n
K = sorted(counts)
V = [counts[k] for k in K]
Z = [0]
t = 0
for v in V:
	t += v
	Z.append(t)
import bisect
for _ in range(Q):
	(L, R) = map(int, input().split())
	x = bisect.bisect_left(K, L)
	y = bisect.bisect_right(K, R)
	print(Z[y] - Z[x])


import collections

class DisjointSet:

	def __init__(self, n):
		self.comm = {x: x for x in range(1, n + 1)}
		self.commsz = {x: 1 for x in range(1, n + 1)}
		self.n = n

	def community(self, a):
		comm = self.comm
		updates = []
		it = a
		while it != comm.get(it, it):
			updates.append(it)
			it = comm.get(it, it)
		for node in updates:
			comm[node] = it
		return it

	def size(self, a):
		return self.commsz[self.community(a)]

	def merge(self, a, b):
		(commsz, comm) = (self.commsz, self.comm)
		(commA, commB) = (self.community(a), self.community(b))
		if commA == commB:
			return
		(big, small) = (commA, commB) if self.size(a) > self.size(b) else (commB, commA)
		result = commsz[big] * commsz[small]
		comm[small] = big
		commsz[big] += commsz[small]
		commsz[small] = 0
		return result

def find(k, arr):
	(l, r) = (0, len(arr))
	m = int((l + r) / 2)
	while l < r and arr[m][0] != k:
		l = m + 1 if arr[m][0] < k else l
		r = r if arr[m][0] < k else m
		m = int((l + r) / 2)
	return (m, r - l)
(N, Q) = list(map(int, input().split()))
edges = sorted([tuple(map(int, input().split())) for _ in range(N - 1)], key=lambda x: x[2])
queries = (tuple(map(int, input().split())) for _ in range(Q))
paths = collections.defaultdict(int)
dset = DisjointSet(N)
for e in edges:
	(u, v, w) = e
	paths[w] += dset.merge(u, v)
paths = [(0, 0)] + sorted(paths.items(), key=lambda x: x[0])
for i in range(1, len(paths)):
	paths[i] = (paths[i][0], paths[i][1] + paths[i - 1][1])
for q in queries:
	(l, r) = q
	l = find(l, paths)[0]
	candidateR = find(r, paths)
	r = candidateR[0] if candidateR[1] else candidateR[0] - 1
	print(paths[r][1] - paths[l - 1][1])


import bisect as bs
(n, q) = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(1, n)]
edges.sort(key=lambda x: x[2])
paths = {}
union = [-1] * n

def getroot(x):
	if union[x] < 0:
		return x
	union[x] = getroot(union[x])
	return union[x]
for (u, v, c) in edges:
	u = getroot(u - 1)
	v = getroot(v - 1)
	paths[c] = paths.get(c, 0) + union[u] * union[v]
	if union[u] < union[v]:
		(u, v) = (v, u)
	union[v] += union[u]
	union[u] = v
paths = list(sorted(paths.items()))
a = [0]
b = [0]
for (x, y) in paths:
	a.append(x)
	b.append(b[-1] + y)
for _ in range(q):
	(l, r) = map(int, input().split())
	print(b[bs.bisect(a, r) - 1] - b[bs.bisect_left(a, l) - 1])


class DisjointSet:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.rank = [1 for i in range(n)]
		self.totalPairs = 0

	def ancestor(self, i):
		if i == self.parent[i]:
			return i
		return self.ancestor(self.parent[i])

	def addLink(self, i, j):
		ai = self.ancestor(i)
		aj = self.ancestor(j)
		if ai == aj:
			return
		best = ai if self.rank[ai] > self.rank[aj] else aj
		ri = self.rank[ai]
		rj = self.rank[aj]
		self.totalPairs -= ri * (ri - 1) // 2 + rj * (rj - 1) // 2
		self.rank[best] = ri + rj
		r = ri + rj
		self.totalPairs += r * (r - 1) // 2
		self.parent[ai] = best
		self.parent[aj] = best
(n, q) = list(map(int, input().strip().split(' ')))
E = []
for _ in range(n - 1):
	(e1, e2, w) = [int(i) for i in input().strip().split(' ')]
	E.append((e1 - 1, e2 - 1, w))
E = sorted(E, key=lambda x: x[2])
L = []
R = []
for _ in range(q):
	(l, r) = [int(i) for i in input().strip().split(' ')]
	L.append(l - 1)
	R.append(r)
P = sorted(L + R)
Q = {}
S = DisjointSet(n)
ind = 0
for p in P:
	if ind >= len(E):
		Q[p] = S.totalPairs
		continue
	while ind < len(E) and E[ind][2] <= p:
		S.addLink(E[ind][0], E[ind][1])
		ind += 1
	Q[p] = S.totalPairs
for i in range(q):
	print(Q[R[i]] - Q[L[i]])


from bisect import *

class Node:

	def __init__(self, val):
		self.rep = self
		self.size = 1
		self.val = val

def union(node1, node2):
	r1 = find(node1)
	r2 = find(node2)
	if r1.size <= r2.size:
		r1.rep = r2
		r2.size += r1.size
	else:
		r2.rep = r1
		r1.size += r2.size

def find(node):
	if node.rep != node:
		node.rep = find(node.rep)
	return node.rep

def binsearch(num):
	(l, r) = (0, len(lengths) - 1)
	while l < r:
		m = (l + r) // 2
		if lengths[m] == num:
			return m
		elif lengths[m] < num:
			l = m + 1
		else:
			r = m - 1
	if lengths[l] > num:
		return l - 1
	return l

def find_le(x):
	i = bisect_right(lengths, x)
	if i:
		return i - 1
	raise ValueError

def find_lt(x):
	i = bisect_left(lengths, x)
	if i:
		return i - 1
	raise ValueError
(n, q) = map(int, input().split())
tree = dict()
for i in range(1, n + 1):
	tree[i] = Node(i)
edges = set()
for i in range(n - 1):
	(v1, v2, c) = map(int, input().split())
	edges.add((c, v1, v2))
edges = sorted(edges)
lengths = [0]
counts = [0]
for (c, v1, v2) in edges:
	count = find(tree[v1]).rep.size * find(tree[v2]).rep.size
	if c != lengths[-1]:
		lengths.append(c)
		counts.append(count)
	else:
		counts[-1] += count
	union(tree[v1], tree[v2])
for i in range(1, len(counts)):
	counts[i] += counts[i - 1]
for _ in range(q):
	(l, r) = map(int, input().split())
	i1 = find_lt(l)
	i2 = find_le(r)
	print(counts[i2] - counts[i1])


from collections import defaultdict

class DisjointSetForest:

	def __init__(self):
		self.node_map = {}

	def make_set(self, key):
		self.node_map[key] = DisjointSetNode(key)

	def find_set(self, key):
		return self._find_set(self.node_map[key])

	def _find_set(self, x):
		if x.parent is not x:
			x.parent = self._find_set(x.parent)
		return x.parent

	def union(self, key1, key2):
		self._union(self.find_set(key1), self.find_set(key2))

	def _union(self, x, y):
		if x is y:
			return
		if x.size > y.size:
			y.parent = x
			y.parent.size += y.size
		else:
			x.parent = y
			x.parent.size += x.size

class DisjointSetNode:

	def __init__(self, key):
		self.key = key
		self.parent = self
		self.rank = 0
		self.size = 1

def initialize_disjoint_set_forest(n):
	disjoint_set_forest = DisjointSetForest()
	for vertex in range(1, N + 1):
		disjoint_set_forest.make_set(vertex)
	return disjoint_set_forest

def binary_search_floor_weight(w, edges):
	if w < edges[0][-1]:
		return 0
	(p, r) = (0, len(edges) - 1)
	while p < r:
		q = (p + r + 1) // 2
		if edges[q][-1] == w:
			return w
		elif edges[q][-1] > w:
			r = q - 1
		else:
			p = q
	return edges[p][-1]
(N, Q) = map(int, input().split())
disjoint_set_forest = initialize_disjoint_set_forest(N)
cumulative_count = {0: 0}
edges = []
for edge_index in range(N - 1):
	edge = tuple(map(int, input().split()))
	edges.append(edge)
edges.sort(key=lambda x: x[-1])
total = 0
for edge in edges:
	weight = edge[-1]
	total += disjoint_set_forest.find_set(edge[0]).size * disjoint_set_forest.find_set(edge[1]).size
	disjoint_set_forest.union(edge[0], edge[1])
	cumulative_count[weight] = total
for query in range(Q):
	(L, R) = map(int, input().split())
	lower_weight = binary_search_floor_weight(L - 1, edges)
	upper_weight = binary_search_floor_weight(R, edges)
	print(cumulative_count[upper_weight] - cumulative_count[lower_weight])


class DisjointSet:

	def __init__(self):
		self.nodes = {}

	def add_value(self, value):
		self.nodes[value] = Node()

	def _get_ult_parent(self, node):
		if node.parent is None:
			return node
		node.parent = self._get_ult_parent(node.parent)
		return node.parent

	def get_group_size(self, node_num):
		return self._get_ult_parent(self.nodes[node_num]).group_size

	def union(self, a, b):
		root_a = self._get_ult_parent(self.nodes[a])
		root_b = self._get_ult_parent(self.nodes[b])
		added_connections = root_a.group_size * root_b.group_size
		if root_a != root_b:
			if root_a.rank > root_b.rank:
				root_b.parent = root_a
				root_a.group_size += root_b.group_size
			elif root_a.rank < root_b.rank:
				root_a.parent = root_b
				root_b.group_size += root_a.group_size
			else:
				root_b.parent = root_a
				root_a.group_size += root_b.group_size
				root_a.rank += 1
		return added_connections

class Node:

	def __init__(self):
		self.parent = None
		self.group_size = 1
		self.rank = 0

def search(L, value, round_down=True):
	(start, stop) = (0, len(L) - 1)
	while stop >= start:
		middle = (start + stop) // 2
		if value == L[middle][0]:
			return middle
		elif value > L[middle][0]:
			start = middle + 1
		else:
			stop = middle - 1
	return stop if round_down else start
(num_nodes, num_queries) = map(int, input().split())
ds = DisjointSet()
for i in range(1, num_nodes + 1):
	ds.add_value(i)
edges = []
for i in range(num_nodes - 1):
	(v1, v2, weight) = map(int, input().split())
	edges.append((weight, v1, v2))
edges.sort()
paths_less_than_weight = [[0, 0]]
previous_weight = 0
for (weight, v1, v2) in edges:
	paths_added = ds.union(v1, v2)
	if weight > previous_weight:
		(_, num_paths) = paths_less_than_weight[-1]
		paths_less_than_weight.append([weight, num_paths + paths_added])
	else:
		paths_less_than_weight[-1][1] += paths_added
	previous_weight = weight
for _ in range(num_queries):
	(L, R) = map(int, input().split())
	R_idx = search(paths_less_than_weight, R)
	L_idx = max(0, search(paths_less_than_weight, L, round_down=False) - 1)
	print(paths_less_than_weight[R_idx][1] - paths_less_than_weight[L_idx][1])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_ge) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_ge[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_ge.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_ge[Ri] - path_count_ge[Li])


[n, q] = map(int, input().strip().split())
(h, s) = ([], [])

def find(t):
	if h[t] != t:
		h[t] = find(h[t])
	return h[t]

def f(n):
	return n * (n - 1) // 2
for i in range(n):
	h.append(i)
	s.append(1)
edge = []
for _ in range(n - 1):
	[u, v, w] = map(int, input().strip().split())
	edge.append([w, u - 1, v - 1])
edge = sorted(edge)
ans = [0] * n
for i in range(n - 1):
	[w, u, v] = edge[i]
	a = find(u)
	b = find(v)
	ans[i + 1] = ans[i]
	if a != b:
		ans[i + 1] += f(s[a] + s[b]) - f(s[a]) - f(s[b])
		h[a] = b
		s[b] += s[a]
		s[a] = 0

def get(k):
	if n == 1 or k < edge[0][0]:
		return 0
	a = 0
	c = n - 2
	while a < c:
		b = (a + c + 1) // 2
		if k >= edge[b][0]:
			a = b
		else:
			c = b - 1
	return ans[a + 1]
for _ in range(q):
	[l, r] = map(int, input().strip().split())
	print(get(r) - get(l - 1))


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import bisect
stin = lambda : list(map(int, input().split()))
(N, Q) = stin()
parents = list(range(N + 1))
sizes = [1] * (N + 1)

def find(x):
	st = list()
	while x != parents[x]:
		st.append(x)
		x = parents[x]
	for y in st:
		parents[y] = x
	return x

def union(x, y):
	ux = find(x)
	uy = find(y)
	if ux != uy:
		parents[uy] = ux
		sizes[ux] += sizes[uy]

def size(x):
	return sizes[find(x)]
edges = list()
for _ in range(N - 1):
	(u, v, w) = stin()
	edges.append((w, u, v))
cnts = dict()
for (w, u, v) in sorted(edges):
	cnts[w] = cnts.get(w, 0) + size(u) * size(v)
	union(u, v)
ps = [0]
ws = [0]
for (w, c) in sorted(cnts.items()):
	ps.append(ps[-1] + c)
	ws.append(w)
bl = bisect.bisect_left
br = bisect.bisect_right
for _ in range(Q):
	(L, R) = stin()
	l = bl(ws, L)
	r = br(ws, R) - 1
	print(ps[r] - ps[l - 1])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
from functools import reduce
import operator as op
import bisect
import itertools
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import bisect
(n, q) = map(int, input().split())
edge = [list(map(int, input().split())) for i in range(n - 1)]
fa = [i for i in range(n + 1)]
cnt = [1] * (n + 1)

def Find(x):
	if fa[x] != x:
		fa[x] = Find(fa[x])
	return fa[x]

def Union(x, y):
	fx = Find(x)
	fy = Find(y)
	if fx != fy:
		fa[fy] = fx
		addition = cnt[fx] * cnt[fy]
		cnt[fx] += cnt[fy]
		return addition
	return 0
edge.sort(key=lambda x: x[2])
edgei = []
edgev = []
current = 0
for i in range(n - 1):
	tmp = Union(edge[i][0], edge[i][1])
	current += tmp
	if i == n - 2 or edge[i][2] < edge[i + 1][2]:
		edgei.append(edge[i][2])
		edgev.append(current)
edgei = [0] + edgei
edgev = [0] + edgev
for i in range(q):
	(l, r) = map(int, input().split())
	idxl = bisect.bisect_left(edgei, l) - 1
	idxr = bisect.bisect_right(edgei, r) - 1
	print(int(edgev[idxr] - edgev[idxl]))


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


def get_class(cl, a):
	x = a
	while True:
		if cl[x] == x:
			return x
		y = cl[x]
		cl[x] = cl[y]
		x = y

def merge_class(cl, size, a, b):
	a_class = get_class(cl, a)
	b_class = get_class(cl, b)
	rv = size[a_class] * size[b_class]
	if size[a_class] < size[b_class]:
		cl[a_class] = b_class
		size[b_class] += size[a_class]
	else:
		cl[b_class] = a_class
		size[a_class] += size[b_class]
	return rv

def bisect(prefix, wt):
	low = 0
	high = len(prefix)
	while True:
		if high == low + 1:
			return prefix[low][1]
		mid = low + (high - low) // 2
		if prefix[mid][0] > wt:
			high = mid
		else:
			low = mid
(num_vertices, num_queries) = (int(x) for x in input().split())
edges = []
for _ in range(num_vertices - 1):
	(a, b, wt) = (int(x) for x in input().split())
	edges.append((wt, a - 1, b - 1))
edges = sorted(edges)
cl = [i for i in range(num_vertices)]
cl_size = [1] * num_vertices
count = [(0, 0)]
for (wt, a, b) in edges:
	c = merge_class(cl, cl_size, a, b)
	if wt == count[-1][0]:
		count[-1] = (wt, c + count[-1][1])
	else:
		count.append((wt, c))
current = 0
prefix = []
for (wt, c) in count:
	current += c
	prefix.append((wt, current))
for _ in range(num_queries):
	(wt1, wt2) = (int(x) for x in input().split())
	c1 = bisect(prefix, wt1 - 1)
	c2 = bisect(prefix, wt2)
	print(c2 - c1)


import bisect

def getparent(p, v, lastpas):
	vv = v
	while p[vv] != vv:
		vv = p[vv]
	while p[v] != v:
		v = p[v]
		p[v] = vv
	return vv

def mergeto(p, c, m, i, lastpas, lt):
	mto = m[i]
	total = lt
	pas = set()
	for s in mto:
		pv = -1
		for v in s:
			if p[v] == 0:
				p[v] = v
			if pv == -1:
				pv = getparent(p, v, lastpas)
				c[pv] = max(1, c[pv])
				pas.add(pv)
			ppv = getparent(p, v, lastpas)
			p[ppv] = pv
			p[v] = pv
			if ppv in lastpas:
				total -= c[ppv] * (c[ppv] - 1) // 2
				lastpas.remove(ppv)
			if v in lastpas:
				total -= c[v] * (c[v] - 1) // 2
				lastpas.remove(v)
			if ppv != pv:
				c[pv] += max(1, c[ppv])
				c[ppv] = 0
		if pv in lastpas:
			lastpas.remove(pv)
		total += c[pv] * (c[pv] - 1) // 2
	lastpas |= pas
	return total
(n, q) = map(int, input().split(' '))
m = {}
for _ in range(n - 1):
	(u, v, c) = map(int, input().split(' '))
	if c not in m:
		m[c] = []
	added = False
	for vv in m[c]:
		if u in vv or v in vv:
			vv.add(u)
			vv.add(v)
			added = True
			break
	if not added:
		m[c].append(set([u, v]))
k = sorted([kk for kk in m])
ans = {0: 0}
p = [0] * (n + 1)
c = [0] * (n + 1)
lp = set()
lt = 0
for i in k:
	total = mergeto(p, c, m, i, lp, lt)
	lt = total
	ans[i] = total
for _ in range(q):
	(st, en) = map(int, input().split(' '))
	b = bisect.bisect_right(k, en)
	if b > 0:
		en = k[b - 1]
	else:
		en = 0
	b = bisect.bisect_right(k, st - 1)
	if b > 0:
		st = k[b - 1]
	else:
		st = 0
	total = ans[en] - ans[st]
	print(total)


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


(n, q) = map(int, input().strip().split(' '))
maxn = 100005

def getpar(i):
	if par[i] == i:
		return i
	par[i] = getpar(par[i])
	return par[i]
edges = []
for _ in range(n - 1):
	(u, v, w) = map(int, input().strip().split(' '))
	u -= 1
	v -= 1
	edges.append((w, u, v))
edges = sorted(edges)
setsize = {}
edges_by_weight = []
last_weight = 0
edges_so_far = 0
par = [i for i in range(n)]
for (weight, i, j) in edges:
	if weight != last_weight:
		edges_by_weight.append((last_weight, edges_so_far))
		last_weight = weight
	par1 = getpar(i)
	par2 = getpar(j)
	if par1 > par2:
		(par1, par2) = (par2, par1)
		(i, j) = (j, i)
	if par1 in setsize:
		set1 = setsize[par1]
	else:
		set1 = 1
	if par2 in setsize:
		set2 = setsize[par2]
	else:
		set2 = 1
	setsize[par1] = set1 + set2
	edges_so_far += set1 * set2
	if par2 in setsize:
		del setsize[par2]
	par[par2] = par1
edges_by_weight.append((last_weight, edges_so_far))

def bisect_right(n):
	hi = len(edges_by_weight)
	lo = 0
	while lo < hi:
		mid = (hi + lo) // 2
		if edges_by_weight[mid][0] > n:
			hi = mid
		else:
			lo = mid + 1
	return lo

def bisect_left(n):
	hi = len(edges_by_weight)
	lo = 0
	while lo < hi:
		mid = (hi + lo) // 2
		if edges_by_weight[mid][0] < n:
			lo = mid + 1
		else:
			hi = mid
	return lo
for _ in range(q):
	(l, r) = map(int, input().strip().split(' '))
	ledge = bisect_left(l)
	redge = bisect_right(r) - 1
	ans = edges_by_weight[redge][1] - edges_by_weight[ledge - 1][1]
	print(ans)


import bisect
from collections import defaultdict
from itertools import accumulate
(n, q) = map(int, input().strip().split())
nodes = [i for i in range(n)]
trees = {i: [i] for i in range(n)}
data = []
for _ in range(n - 1):
	(u, v, w) = map(int, input().strip().split())
	u -= 1
	v -= 1
	bisect.insort_left(data, (w, u, v))
costs = defaultdict(int)
for (w, u, v) in data:
	source = nodes[u]
	i = len(trees[source])
	dest = nodes[v]
	j = len(trees[dest])
	costs[w] += i * j
	if i > j:
		(source, dest) = (source, dest)
	for index in trees[source]:
		nodes[index] = dest
	trees[dest].extend(trees[source])
	del trees[source]
(costs, paths) = zip(*sorted(costs.items()))
answers = list(accumulate(paths))
for _ in range(q):
	(l, r) = map(int, input().strip().split())
	a = bisect.bisect_left(costs, l)
	b = bisect.bisect_right(costs, r)
	print(answers[b - 1] - answers[a - 1] * (a > 0))


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import pdb
import sys
from bisect import bisect

class Components(object):

	def __init__(self, N):
		self.parent = [-1] * N
		self.count = [1] * N

	def add(self, i, j):
		i = self.get_root(i)
		j = self.get_root(j)
		self.parent[j] = i
		incr = self.count[i] * self.count[j]
		self.count[i] += self.count[j]
		return incr

	def get_root(self, i):
		while self.parent[i] != -1:
			i = self.parent[i]
		return i

def gen_paths_upto(G, N):
	max_w = max([x[2] for x in G])
	le_counts = {}
	G1 = sorted(G, key=lambda x: x[2])
	CC = Components(N)
	c_count = 0
	c_wt = 0
	n = 0
	for (i, j, w) in G1:
		incr = CC.add(i, j)
		c_count += incr
		le_counts[w] = c_count
		c_wt = w
		n += 1
	le_tree = None
	le_items = sorted(list(le_counts.items()), key=lambda x: x[0])
	return (list(map(lambda x: x[0], le_items)), list(map(lambda x: x[1], le_items)))

def query(low, high, le_keys, le_values):
	left = low - 1
	right = high
	lidx = bisect(le_keys, left)
	lval = le_values[lidx - 1] if lidx > 0 else 0
	ridx = bisect(le_keys, right)
	rval = le_values[ridx - 1]
	return rval - lval

def read_inputs(fd):
	(N, queries) = list(map(int, fd.readline().strip().split(' ')))
	G = []
	for i in range(N - 1):
		(src, tgt, ewt) = list(map(int, fd.readline().strip().split(' ')))
		G.append((src - 1, tgt - 1, ewt))
	Q = []
	for i in range(queries):
		(low, high) = list(map(int, fd.readline().strip().split(' ')))
		Q.append((low, high))
	return (G, N, Q)
fd = open(sys.argv[1]) if len(sys.argv) > 1 else sys.stdin
(G, N, Q) = read_inputs(fd)
(le_keys, le_values) = gen_paths_upto(G, N)
for (low, high) in Q:
	print(query(low, high, le_keys, le_values))


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import bisect
inpt = list(map(int, input().split()))
(n, q) = (inpt[0], inpt[1])
edges = []
root = [0] * 100009
sz = [1] * 100009
rank = [0] * 100009
for i in range(n):
	root[i + 1] = i + 1
	rank[i + 1] = 1

def parent(node):
	if root[node] == node:
		return node
	root[node] = parent(root[node])
	return root[node]

def union(a, b):
	a = parent(a)
	b = parent(b)
	if a == b:
		return
	if rank[a] > rank[b]:
		(a, b) = (b, a)
	sz[b] += sz[a]
	root[a] = b
	if rank[a] == rank[b]:
		rank[b] = rank[b] + 1
for i in range(n - 1):
	inpt = list(map(int, input().split()))
	edges.append((inpt[0], inpt[1], inpt[2]))
edges.sort(key=lambda x: x[2])
dic = []
psums = []
for i in range(n - 1):
	(start, end, weight) = edges[i]
	count_start = sz[parent(start)]
	count_end = sz[parent(end)]
	dic.append(weight)
	psums.append(count_start * count_end)
	union(start, end)
for i in range(1, len(dic)):
	psums[i] += psums[i - 1]
maxW = psums[n - 2]
minW = psums[0]
for i in range(q):
	inpt = list(map(int, input().split()))
	lower = bisect.bisect_left(dic, inpt[0])
	higher = bisect.bisect_right(dic, inpt[1])
	answer = 0
	if higher < minW and lower > maxW:
		answer = 0
	else:
		answer = psums[higher - 1] - (psums[lower - 1] if lower > 0 else 0)
	print(answer)


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


from collections import defaultdict
from itertools import groupby
from operator import itemgetter
from bisect import bisect_left, bisect_right

class UnionFind:

	def __init__(self):
		self.leaders = defaultdict(lambda : None)
		self.groups = defaultdict(set)
		self.combs = defaultdict(int)
		self.total_combs = 0

	def find(self, x):
		l = self.leaders[x] or x
		if x in self.groups[l]:
			self.groups[l].remove(x)
			self.update_combs(l)
		if l != x:
			while self.leaders[l] is not None:
				l = self.leaders[l]
			self.leaders[x] = l
		self.groups[l].add(x)
		self.update_combs(l)
		return l

	def union(self, x, y):
		(lx, ly) = (self.find(x), self.find(y))
		if lx != ly:
			self.leaders[lx] = ly
			self.groups[ly] |= self.groups.pop(lx)
			self.update_combs(ly)
			self.update_combs(lx)

	def update_combs(self, g):
		x = len(self.groups[g])
		self.total_combs -= self.combs[g]
		self.combs[g] = x * (x - 1) // 2
		self.total_combs += self.combs[g]
(n, q) = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
queries = [tuple(map(int, input().split())) for _ in range(q)]
uf = UnionFind()
combs = {0: 0}
for (k, g) in groupby(sorted(edges, key=itemgetter(2)), key=itemgetter(2)):
	for (x, y, w) in g:
		uf.union(x, y)
	combs[k] = uf.total_combs
weights = sorted(combs)
for (l, r) in queries:
	lower = weights[bisect_left(weights, l) - 1]
	high = weights[bisect_right(weights, r) - 1]
	print(combs[high] - combs[lower])


import os
import sys
import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


from bisect import bisect_left, bisect_right
import sys
reader = iter(sys.stdin.readlines())
(n, q) = map(int, next(reader).split())
edges = [(*map(int, next(reader).split()),) for _ in range(n - 1)]
queries = ((*map(int, next(reader).split()),) for _ in range(q))
edges.sort(key=lambda el: el[2])

def n_paths(n_vertices):
	return n_vertices * (n_vertices - 1) // 2

def comp_id(v):
	j = v
	while uf[v] != v:
		v = uf[v]
	while uf[j] != v:
		(j, uf[j]) = (uf[j], v)
	return v

def unite(v1, v2):
	id1 = comp_id(v1)
	id2 = comp_id(v2)
	less = n_paths(ns[id1]) + n_paths(ns[id2])
	uf[id2] = id1
	ns[id1] += ns[id2]
	return n_paths(ns[id1]) - less

def process(stack):
	res = 0
	while stack:
		(u, v) = stack.pop()
		res += unite(u - 1, v - 1)
	return res
uf = [*range(n)]
ns = [1] * n
sorted_weights = [edges[0][2]]
count_paths = [0]
stack = []
for (u, v, w) in edges:
	if w == sorted_weights[-1]:
		stack.append((u, v))
		continue
	count_paths.append(count_paths[-1] + process(stack))
	assert not stack
	sorted_weights.append(w)
	stack.append((u, v))
count_paths.append(count_paths[-1] + process(stack))
assert count_paths[-1] == n_paths(n)
for (l, r) in queries:
	lix = bisect_left(sorted_weights, l)
	rix = bisect_right(sorted_weights, r)
	print(count_paths[rix] - count_paths[lix])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


from collections import defaultdict
import bisect

class cluster:

	def __init__(self, x):
		self.parent = self
		self.name = x
		self.rank = 1
		self.size = 1

def find(x):
	while x.parent != x:
		nxt = x.parent
		x.parent = nxt.parent
		x = nxt
	return x

def merge(x, y):
	if x == y:
		return x
	if x.rank < y.rank:
		(x, y) = (y, x)
	y.parent = x
	if x.rank == y.rank:
		x.rank += 1
	x.size += y.size
(n, q) = map(int, input().split())
edges = []
nodes = {x: cluster(x) for x in range(1, n + 1)}
distances = defaultdict(int)
distances[0] = 0
for i in range(n - 1):
	(x, y, w) = map(int, input().split())
	edges.append((w, x, y))
edges.sort()
for (w, x, y) in edges:
	x = find(nodes[x])
	y = find(nodes[y])
	distances[w] += x.size * y.size
	merge(x, y)
values = list(distances.keys())
values.sort()
for i in range(1, len(values)):
	distances[values[i]] += distances[values[i - 1]]
for j in range(q):
	(l, r) = map(int, input().split())
	ind_l = bisect.bisect_left(values, l)
	ind_r = bisect.bisect_right(values, r)
	print(distances[values[ind_r - 1]] - distances[values[ind_l - 1]])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import bisect as bs
(n, q) = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(1, n)]
edges.sort(key=lambda x: x[2])
paths = {}
union = [-1] * n

def getroot(x):
	if union[x] < 0:
		return x
	union[x] = getroot(union[x])
	return union[x]
for (u, v, c) in edges:
	u = getroot(u - 1)
	v = getroot(v - 1)
	paths[c] = paths.get(c, 0) + union[u] * union[v]
	if union[u] < union[v]:
		(u, v) = (v, u)
	union[v] += union[u]
	union[u] = v
paths = list(sorted(paths.items()))
a = [0]
b = [0]
for (x, y) in paths:
	a.append(x)
	b.append(b[-1] + y)
for _ in range(q):
	(l, r) = map(int, input().split())
	print(b[bs.bisect(a, r) - 1] - b[bs.bisect_left(a, l) - 1])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


from collections import defaultdict
(N, Q) = map(int, input().split())
weights = []
for _ in range(N - 1):
	(U, V, W) = map(int, input().split())
	weights.append([W, U, V])
weights.sort()

class Node:

	def __init__(self, size, parent=None):
		self.size = size
		self.parent = parent
clusters = {n: Node(1) for n in range(1, N + 1)}
counts = defaultdict(int)
for (W, U, V) in weights:
	u = clusters[U]
	v = clusters[V]
	while u.parent:
		u = u.parent
	while v.parent:
		v = v.parent
	counts[W] += u.size * v.size
	n = Node(u.size + v.size)
	u.parent = n
	v.parent = n
	clusters[U] = n
	clusters[V] = n
K = sorted(counts)
V = [counts[k] for k in K]
Z = [0]
t = 0
for v in V:
	t += v
	Z.append(t)
import bisect
for _ in range(Q):
	(L, R) = map(int, input().split())
	x = bisect.bisect_left(K, L)
	y = bisect.bisect_right(K, R)
	print(Z[y] - Z[x])


from collections import defaultdict
(N, Q) = map(int, input().split())
weights = []
for _ in range(N - 1):
	(U, V, W) = map(int, input().split())
	weights.append([W, U, V])
weights.sort()

class Node:

	def __init__(self, size, parent=None):
		self.size = size
		self.parent = parent
clusters = {n: Node(1) for n in range(1, N + 1)}
counts = defaultdict(int)
for (W, U, V) in weights:
	u = clusters[U]
	v = clusters[V]
	while u.parent:
		u = u.parent
	while v.parent:
		v = v.parent
	counts[W] += u.size * v.size
	n = Node(u.size + v.size)
	u.parent = n
	v.parent = n
	clusters[U] = n
	clusters[V] = n
K = sorted(counts)
V = [counts[k] for k in K]
Z = [0]
t = 0
for v in V:
	t += v
	Z.append(t)
import bisect
for _ in range(Q):
	(L, R) = map(int, input().split())
	x = bisect.bisect_left(K, L)
	y = bisect.bisect_right(K, R)
	print(Z[y] - Z[x])


import bisect as bs
(n, q) = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(1, n)]
edges.sort(key=lambda x: x[2])
paths = {}
union = [-1] * n

def getroot(x):
	if union[x] < 0:
		return x
	union[x] = getroot(union[x])
	return union[x]
for (u, v, c) in edges:
	u = getroot(u - 1)
	v = getroot(v - 1)
	paths[c] = paths.get(c, 0) + union[u] * union[v]
	if union[u] < union[v]:
		(u, v) = (v, u)
	union[v] += union[u]
	union[u] = v
paths = list(sorted(paths.items()))
a = [0]
b = [0]
for (x, y) in paths:
	a.append(x)
	b.append(b[-1] + y)
for _ in range(q):
	(l, r) = map(int, input().split())
	print(b[bs.bisect(a, r) - 1] - b[bs.bisect_left(a, l) - 1])


from bisect import bisect_left, bisect_right
(n, q) = map(int, input().split())
t = []
qy = []
for i in range(n - 1):
	t.append(list(map(int, input().split())))
for i in range(q):
	qy.append(list(map(int, input().split())))
t.sort(key=lambda x: x[2])
l = [-1 for _ in range(n + 1)]

def find():
	s = 0
	for i in l:
		if i < -1:
			s += -i * (-1 - i) // 2
	return s
r = []
s = 0
flag = 1
for i in t:
	x = i[0]
	y = i[1]
	while l[x] > 0:
		x = l[x]
	while l[y] > 0:
		y = l[y]
	if flag == 1:
		l[y] += l[x]
		l[x] = y
		flag = 0
		s = find()
	else:
		s += -l[x] * -l[y]
		l[y] += l[x]
		l[x] = y
	r.append(s)
s1 = 0
s2 = 0
b = [i[2] for i in t]
for j in qy:
	s1 = 0
	s2 = 0
	if bisect_right(b, j[0] - 1) - 1 >= 0:
		s1 = r[bisect_right(b, j[0] - 1) - 1]
	else:
		s1 = 0
	s2 = r[bisect_right(b, j[1]) - 1]
	print(s2 - s1)


from bisect import bisect_left, bisect_right
(n, q) = map(int, input().split())
t = []
qy = []
for i in range(n - 1):
	t.append(list(map(int, input().split())))
for i in range(q):
	qy.append(list(map(int, input().split())))
t.sort(key=lambda x: x[2])
l = [-1 for _ in range(n + 1)]

def find():
	s = 0
	for i in l:
		if i < -1:
			s += -i * (-1 - i) // 2
	return s
r = []
s = 0
flag = 1
for i in t:
	x = i[0]
	y = i[1]
	while l[x] > 0:
		x = l[x]
	while l[y] > 0:
		y = l[y]
	if flag == 1:
		l[y] += l[x]
		l[x] = y
		flag = 0
		s = find()
	else:
		s += -l[x] * -l[y]
		l[y] += l[x]
		l[x] = y
	r.append(s)
s1 = 0
s2 = 0
b = [i[2] for i in t]
for j in qy:
	s1 = 0
	s2 = 0
	if bisect_right(b, j[0] - 1) - 1 >= 0:
		s1 = r[bisect_right(b, j[0] - 1) - 1]
	else:
		s1 = 0
	s2 = r[bisect_right(b, j[1]) - 1]
	print(s2 - s1)


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])


import itertools
import bisect

class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N
		self.path_total = [0] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			new_paths = self.total[a_parent] * self.total[b_parent]
			self.path_total[a_parent] += self.path_total[b_parent] + new_paths
			self.total[a_parent] += self.total[b_parent]
			return new_paths
		else:
			return 0

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

	def get_total(self, a):
		return self.total[self.find(a)]
(N, Q) = map(int, input().split())
ds = DisjointSet(N)
paths = [list(map(int, input().split())) for i in range(N - 1)]
paths.sort(key=lambda x: x[2])
(path_lengths, path_count_le) = ([0], [0])
for (length, l) in itertools.groupby(paths, key=lambda x: x[2]):
	total = path_count_le[-1]
	for path in l:
		total += ds.union(path[0] - 1, path[1] - 1)
	path_lengths.append(length)
	path_count_le.append(total)
for i in range(Q):
	(L, R) = map(int, input().split())
	Li = bisect.bisect(path_lengths, L - 1) - 1
	Ri = bisect.bisect(path_lengths, R) - 1
	print(path_count_le[Ri] - path_count_le[Li])