Вам дано корневое дерево, состоящее из $$$n$$$ вершин. Вершины пронумерованы от $$$1$$$ до $$$n$$$, а корнем является вершина $$$1$$$. Также вам дан массив коэффициентов $$$s_1, s_2, \ldots, s_n$$$.
Мультимножество из $$$k$$$ простых путей называется допустимым, если выполняются следующие два условия:
Можно показать, что всегда можно найти хотя бы одно допустимое мультимножество. Найдите максимальное значение среди всех допустимых мультимножеств.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.
Первая строка каждого набора входных данных содержит два целых числа через пробел $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) и $$$k$$$ ($$$1 \le k \le 10^9$$$) — размер дерева и требуемое количество путей.
Вторая строка содержит $$$n - 1$$$ целое число через пробел $$$p_2,p_3,\ldots,p_n$$$ ($$$1\le p_i\le n$$$), где $$$p_i$$$ — родитель $$$i$$$-й вершины. Гарантируется, что данные значения корректно задают дерево с корнем в $$$1$$$.
В третьей строке через пробел записаны $$$n$$$ целых чисел $$$s_1,s_2,\ldots,s_n$$$ ($$$0 \le s_i \le 10^4$$$) — коэффициенты вершин.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10 ^ 5$$$.
Для каждого набора входных данных выведите одно целое число — максимальное значение мультимножества.
25 41 2 1 36 2 1 5 75 31 2 1 36 6 1 4 10
54 56
В первом наборе входных данных одно из оптимальных решений — четыре пути $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 4$$$, $$$1 \to 4$$$, при этом $$$c=[4,2,2,2,2]$$$. Значение будет равно $$$4\cdot 6+ 2\cdot 2+2\cdot 1+2\cdot 5+2\cdot 7=54$$$.
Во втором наборе входных данных одно из оптимальных решений — три пути $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 2 \to 3 \to 5$$$, $$$1 \to 4$$$, при этом $$$c=[3,2,2,1,2]$$$. Значение будет равно $$$3\cdot 6+ 2\cdot 6+2\cdot 1+1\cdot 4+2\cdot 10=56$$$.
| Codeforces Global Round 23 |
|---|
| Закончено |
