P15048 [UOI 2022 II Stage] Tree 2

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.

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 $m$ integers $x_1, x_2, \dots, x_m$, where $x_i$ is the answer to the $i$-th query.

### 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