Path Queries

题意翻译

### 题目描述 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 有一棵 $n$ 个点的树，每条边都带权。 她会问你 $m$ 个问题，每次给你一个正整数 $q$，求最大权值不大于 $q$ 的简单路径数量。 需要注意的是，对于一个点对 $(u,v)$ 只记一次，单独一个点不算路径。 ### 输入格式 第一行两个正整数 $n,m$，意义如题目描述。 接下来 $n-1$ 行，每行三个正整数 $u,v,w$，表示 $u,v$ 之间有一条权为 $w$ 的无向边。 最后一行 $m$ 个正整数，表示询问。 ### 输出格式 对于每个询问，输出一行一个整数表示答案。 ### 数据范围 $1\le n,m \le 2\times10^5$ $1\le u,v \le n$ $1\le w,q \le 2\times 10^5$

题目描述

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 $ .

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #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 

输入样例 #2

1 2
1 2

输出样例 #2

0 0 

输入样例 #3

3 3
1 2 1
2 3 2
1 3 2

输出样例 #3

1 3 3 

说明

The picture shows the tree from the first example: 

题意翻译

### 题目描述 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 有一棵 $n$ 个点的树，每条边都带权。 她会问你 $m$ 个问题，每次给你一个正整数 $q$，求最大权值不大于 $q$ 的简单路径数量。 需要注意的是，对于一个点对 $(u,v)$ 只记一次，单独一个点不算路径。 ### 输入格式 第一行两个正整数 $n,m$，意义如题目描述。 接下来 $n-1$ 行，每行三个正整数 $u,v,w$，表示 $u,v$ 之间有一条权为 $w$ 的无向边。 最后一行 $m$ 个正整数，表示询问。 ### 输出格式 对于每个询问，输出一行一个整数表示答案。 ### 数据范围 $1\le n,m \le 2\times10^5$ $1\le u,v \le n$ $1\le w,q \le 2\times 10^5$