Козак Вус та дерево#11075

Козак Вус та дерево

2 секунди

512 мегабайтів

Середня

Козак Вус побачив дерево, коли повертався додому із залізничної дороги та придумав задачу.

Задане дерево на $n$ вершинах, кожне ребро якого має певну вагу. Спочатку всі його вершини білі. Назвемо ребро яскравим, якщо воно з'єднує дві білі вершини. Дайте відповідь на $m$ запитів:

Яку найменшу кількість вершин необхідно перефарбувати у чорний колір, щоб сумарна вага всіх яскравих ребер не перевищувала $k_{i}$ k_i?

Допоможіть Козаку Вусу розв'язати цю задачу.

Вхідні дані

Перший рядок містить три цілі числа $n$ , $m$ та $g$ ( $1 \leq n \leq 3000$ 1 \leq n \leq 3\,000, $1 \leq m \leq 2 \cdot 1 0^{5}$ 1 \leq m \leq 2 \cdot 10^5, $0 \leq g \leq 6$ 0 \leq g \leq 6) — кількість вершин, кількість запитів та номер блока.

Кожен з наступних $n - 1$ n-1 рядків містить по три цілі числа $u_{i}$ u_i, $v_{i}$ v_i, $c_{i}$ c_i ( $1 \leq v_{i}, u_{i} \leq n$ 1 \leq v_i, u_i \leq n, $1 \leq c_{i} \leq 1 0^{5}$ 1 \leq c_i \leq 10^5) — вершини, які з'єднує ребро, і його вага.

Четвертий рядок містить $m$ цілих чисел $k_{1}, k_{2}, \dots, k_{m}$ k_1, k_2, \dots, k_m ( $0 \leq k_{i} \leq 1 0^{9}$ 0 \leq k_i \leq 10^9).

Вихідні дані

Виведіть $m$ цілих чисел $x_{1}, x_{2}, \dots, x_{m}$ x_1, x_2, \dots, x_m, де $x_{i}$ x_i — відповідь на $i$ -й запит.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі якщо $k_{i} \geq 5$ k_i \geq 5, то можемо залишити всі вершини білими, тоді всі ребра яскраві і сума їхніх ваг рівна $5$ . Для $k_{i} \leq 4$ k_i \leq 4 можемо пофарбувати вершину номер $1$ у чорний колір, тоді яскравих ребер не буде, а отже сума ваг рівна $0$ . В обох цих випадках сума ваг яскравих ребер не перевищує $k_{i}$ k_i і перефарбовано мінімальну кількість вершин.

Оцінювання

( $5$ балів): $m = 1$ m=1; гарантується, що відповідь не перевищує $1$ .
( $9$ балів): $m = 1$ m=1; гарантується, що відповідь не перевищує $2$ .
( $28$ балів): $u_{i} = v_{i} - 1$ u_i = v_i - 1; $n \leq 200$ n \leq 200.
( $14$ балів): $m = 1$ m=1; $n \leq 10$ n \leq 10;
( $21$ бал): $n \leq 200$ n \leq 200;
( $23$ бали): без додаткових обмежень.