Problem Description

Cossack Moustache saw a tree on his way home from the railway, and came up with a problem.

You are given a tree with $n$ vertices, and each edge has a weight. Initially, all vertices are white. We call an edge a bright edge if and only if it connects two white vertices. Please answer $m$ queries:

• What is the minimum number of vertices that need to be recolored to black so that the sum of weights of all bright edges does not exceed $k_i$?

Please help Cossack Moustache solve this problem.

Input Format

The first line contains three integers $n$, $m$, and $g$ ($1 \leq n \leq 3\,000$, $1 \leq m \leq 2 \cdot 10^5$, $0 \leq g \leq 6$), which represent the number of vertices, the number of queries, and the subtask ID, respectively.

In the next $n - 1$ lines, each line contains three integers $u_i$, $v_i$, and $c_i$ ($1 \leq v_i, u_i \leq n$, $1 \leq c_i \leq 10^5$), which describe an edge between the two vertices and its weight.

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

Output Format

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

3 5 0
1 2 3
1 3 2
3 5 1 2 0

1 0 1 1 1

4 4 0
1 3 10
2 1 15
1 4 50
75 50 72 19

0 1 1 1

5 8 0
1 4 5
2 1 18
1 3 9
3 5 27
5 15 7 19 20 58 35 27

2 2 2 2 2 1 1 1

Hint

Sample Explanation

In the first sample, if $k_i \geq 5$, we can keep all vertices white. Then all edges are bright edges, and the sum of their weights is $5$. If $k_i \leq 4$, we can recolor vertex $1$ to black, so there will be no bright edges, and thus the sum of weights is $0$. In both cases, the sum of weights of bright edges does not exceed $k_i$, and the number of recolored vertices is minimal.

Scoring

• (5 points): $m = 1$; the answer is guaranteed to be at most $1$.
• (9 points): $m = 1$; the answer is guaranteed to be at most $2$.
• (28 points): $u_i = v_i - 1$; $n \leq 200$.
• (14 points): $m = 1$; $n \leq 10$.
• (21 points): $n \leq 200$.
• (23 points): No additional constraints.

Translated by DeepSeek V3.

Translated by ChatGPT 5