Codeforces Round 582 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

divide and conquer

dsu

graphs

sortings

trees

*1800

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Path Queries

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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:

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/13/2024 10:16:10 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|