D. Пути на дереве
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано корневое дерево, состоящее из $$$n$$$ вершин. Вершины пронумерованы от $$$1$$$ до $$$n$$$, а корнем является вершина $$$1$$$. Также вам дан массив коэффициентов $$$s_1, s_2, \ldots, s_n$$$.

Мультимножество из $$$k$$$ простых путей называется допустимым, если выполняются следующие два условия:

  • Каждый путь начинается в вершине $$$1$$$.
  • Пусть $$$c_i$$$ — количество путей, покрывающих вершину $$$i$$$. Для каждой пары вершин $$$(u,v)$$$ ($$$2\le u,v\le n$$$), имеющих общего родителя, верно $$$|c_u-c_v|\le 1$$$.
Значение мультимножества путей определяется как $$$\sum\limits_{i=1}^n c_i s_i$$$.

Можно показать, что всегда можно найти хотя бы одно допустимое мультимножество. Найдите максимальное значение среди всех допустимых мультимножеств.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное значение мультимножества.

Пример
Входные данные
2
5 4
1 2 1 3
6 2 1 5 7
5 3
1 2 1 3
6 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$$$.