路径询问（path）

题目描述

给定一棵带权树，共有 $n$ 个节点。

树是一张连通且无环的无向图。

第 $i$ 条边连接节点 $u_i$ 和 $v_i$，边权为 $w_i$。

现在有 $m$ 次询问。第 $i$ 次询问给出一个整数 $q_i$，你需要计算有多少对不同节点 $(u,v)$ 满足：

$$u < v$$

并且从 $u$ 到 $v$ 的简单路径上，所有边权的最大值不超过 $q_i$。

换句话说，对于每个询问 $q_i$，要求统计满足下面条件的点对数量：

$$\max_{e\in path(u,v)} w_e \le q_i$$

输入格式

第一行包含两个整数 $n,m$，分别表示树的节点数量和询问数量。

接下来 $n-1$ 行，每行包含三个整数 $u_i,v_i,w_i$，表示一条无向边。

最后一行包含 $m$ 个整数：

$$q_1,q_2,\ldots,q_m$$

表示所有询问。

保证给出的边构成一棵树。

输出格式

输出 $m$ 个整数，表示每次询问的答案。

第 $i$ 个输出值应等于第 $i$ 次询问中，满足路径最大边权不超过 $q_i$ 的点对 $(u,v)$ 数量。

询问的答案必须按照输入顺序输出。

相邻两个整数之间用一个空格隔开。

输入输出样例 #1

输入 #1

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

输出 #1

21 7 15 21 3

样例解释 #1

共有 $7$ 个节点。

对于询问 $q=1$，只保留边权不超过 $1$ 的边：

$$1-2,\quad 2-4$$

此时节点 $1,2,4$ 可以形成：

$$\binom{3}{2}=3$$

对点对，所以答案为 $3$。

输入输出样例 #2

输入 #2

1 2
1 2

输出 #2

0 0

样例解释 #2

只有 $1$ 个节点，没有任意一对不同节点。

因此无论询问值是多少，答案都是 $0$。

输入输出样例 #3

输入 #3

3 3
1 2 1
2 3 2
1 3 2

输出 #3

1 3 3

样例解释 #3

这棵树有 $3$ 个节点，边为：

$$1-2,\quad 2-3$$

边权分别为 $1$ 和 $2$。

对于询问 $q=1$，只有点对 $(1,2)$ 满足条件，答案为 $1$。

数据范围与约定

对于所有测试数据，保证：

$$1 \le n,m \le 2\times 10^5,1 \le w_i \le 2\times 10^5,1 \le q_i \le 2\times 10^5 $$$$1 \le u_i,v_i \le n,\quad u_i\ne v_i$$

保证给出的边构成一棵树。

测试点	分值	$n$	$m$	特殊性质
$1\sim 2$	$10$	$\le 20$		无
$3\sim 5$	$15$	$\le 10^3$		$\text{A}$
$6\sim 8$				$\text{B}$
$9\sim 12$	$20$	$\le 5\times 10^4$		无
$13\sim 16$		$\le 10^5$
$17\sim 20$		$\le 2\times 10^5$

特殊性质 $\text{A}$：保证这棵树是一条链。

特殊性质 $\text{B}$：保证所有边权都相同。