Cossack Vus and the Tree

Kozak Vus encountered a tree on his way home from the railway station and devised an intriguing problem.

Consider a tree with $n$ vertices, where each edge has a specific weight. Initially, all vertices are colored white. An edge is termed "bright" if it connects two white vertices. You need to answer $m$ queries, each asking:

• What is the minimum number of vertices that must be repainted black so that the total weight of all bright edges does not exceed $k_i$?

Assist Kozak Vus in solving this problem.

Giriş verilənləri

The first line contains three integers $n$, $m$, and $g$ ($1\le n\le 3,000$, $1\le m\le 2\cdot 10^5$, $0\le g\le 6$) — representing the number of vertices, the number of queries, and the block number, respectively.

Each of the following $n-1$ lines contains three integers $u_i$, $v_i$, $c_i$ ($1\le v_i,u_i\le n$, $1\le c_i\le 10^5$) — indicating the vertices connected by the edge and its weight.

The fourth line contains $m$ integers $k_1,k_2,\dots ,k_m$ ($0\le k_i\le 10^9$).

Çıxış verilənləri

Output $m$ integers $x_1,x_2,\dots ,x_m$, where $x_i$ is the answer to the $i$-th query.

Nümunələr

Qeyd

In the first example, if $k_i\ge 5$, all vertices can remain white, making all edges bright with a total weight of $5$. For $k_i\le 4$, painting vertex number $1$ black results in no bright edges, thus the total weight is $0$. In both scenarios, the sum of the weights of the bright edges does not exceed $k_i$, and the minimum number of vertices is repainted.

Qiymətləndirmə

1. ($5$ points): $m=1$; it is guaranteed that the answer does not exceed $1$.

2. ($9$ points): $m=1$; it is guaranteed that the answer does not exceed $2$.

3. ($28$ points): $u_i=v_i-1$; $n\le 200$.

4. ($14$ points): $m=1$; $n\le 10$;

5. ($21$ points): $n\le 200$;

6. ($23$ points): no additional constraints.