Problems
Козак Вус та дерево
Козак Вус та дерево
Козак Вус побачив дерево, коли повертався додому із залізничної дороги та придумав задачу.
Задане дерево на $n$ вершинах, кожне ребро якого має певну вагу. Спочатку всі його вершини білі. Назвемо ребро яскравим, якщо воно з'єднує дві білі вершини. Дайте відповідь на $m$ запитів:
\begin{itemize}
\item Яку найменшу кількість вершин необхідно перефарбувати у чорний колір, щоб сумарна вага всіх яскравих ребер не перевищувала $k_i$?
\end{itemize}
Допоможіть Козаку Вусу розв'язати цю задачу.
\InputFile
Перший рядок містить три цілі числа $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$).
\OutputFile
Виведіть $m$ цілих чисел $x_1, x_2, \dots, x_m$, де $x_i$ --- відповідь на $i-й$ запит.
\Note
У першому прикладі якщо $k_i \geq 5$, то можемо залишити всі вершини білими, тоді всі ребра яскраві і сума їхніх ваг рівна $5$. Для $k_i \leq 4$ можемо пофарбувати вершину номер $1$ у чорний колір, тоді яскравих ребер не буде, а отже сума ваг рівна $0$. В обох цих випадках сума ваг яскравих ребер не перевищує $k_i$ і перефарбовано мінімальну кількість вершин.
\Scoring
\begin{enumerate}
\item ($5$ балів): $m=1$; гарантується, що відповідь не перевищує $1$.
\item ($9$ балів): $m=1$; гарантується, що відповідь не перевищує $2$.
\item ($28$ балів): $u_i = v_i - 1$; $n \leq 200$.
\item ($14$ балів): $m=1$; $n \leq 10$;
\item ($21$ бал): $n \leq 200$;
\item ($23$ бали): без додаткових обмежень.
\end{enumerate}
Input example #1
3 5 0 1 2 3 1 3 2 3 5 1 2 0
Output example #1
1 0 1 1 1
Input example #2
4 4 0 1 3 10 2 1 15 1 4 50 75 50 72 19
Output example #2
0 1 1 1
Input example #3
5 8 0 1 4 5 2 1 18 1 3 9 3 5 27 5 15 7 19 20 58 35 27
Output example #3
2 2 2 2 2 1 1 1