Козак Вус та дерево
ліміт часу на тест
2 seconds
ліміт використання пам'яті на тест
512 megabytes
введення
standard input
виведення
standard output

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

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

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

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

Вхідні дані

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

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

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

Вихідні дані

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

Система оцінки

1. ($$$5$$$ балів): $$$m=1$$$; гарантується, що відповідь не перевищує $$$1$$$.

2. ($$$9$$$ балів): $$$m=1$$$; гарантується, що відповідь не перевищує $$$2$$$.

3. ($$$28$$$ балів): $$$u_i = v_i - 1$$$; $$$n \leq 200$$$.

4. ($$$14$$$ балів): $$$m=1$$$; $$$n \leq 10$$$;

5. ($$$21$$$ бал): $$$n \leq 200$$$;

6. ($$$23$$$ бали): без додаткових обмежень.

Приклади

Вхідні дані

    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

Пояснення

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