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

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

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

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

Вхідні дані

Перший рядок містить три цілі числа $$$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$$$ і перефарбовано мінімальну кількість вершин.