Далекая страна содержит $$$n$$$ городов, соединенных $$$n - 1$$$ дорогами, при этом из любого города можно добраться до любого другого по дорогам страны.
Известно, что каждый город относится ровно к одной провинции. Город $$$v$$$ относится к провинции $$$t_v$$$. Обратите внимание, что конкретная провинция может являться любым подмножеством городов, и возможно из одного города провинции нельзя добраться до другого этой же провинции, проходя только через города этой провинции. Столицей является город номер $$$1$$$.
Банда разбойников собирается грабить караваны, которые будут идти через города страны. У каждого города есть коэффициент того, насколько удобно в нем грабить. В городе $$$v$$$ он равен $$$c_v$$$.
Вам приходят запросы двух типов:
Определите максимальный ущерб, равный количеству награбленного разбойниками, для каждого запроса второго типа. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен $$$0$$$.
В первой строке даны два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 200\,000, 1 \le q \le 200\,000$$$) — количество городов и количество запросов.
Во второй строке дано $$$n - 1$$$ целое число $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i < i$$$), где число $$$p_i$$$ означает, что существует дорога между городами $$$i$$$ и $$$p_i$$$.
В третьей строке дано $$$n$$$ целых чисел $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le t_i \le n$$$) — номера провинций у городов.
В четвертой строке дано $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — коэффициенты успешности грабежа.
Далее идет $$$q$$$ строк описаний запросов. В начале каждой строки дано одно целое число $$$x_i$$$ ($$$1 \le x_i \le 2$$$) — тип запроса.
На каждый запрос второго типа выведите одно число — максимальное число, которое разбойники смогут получить. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен $$$0$$$.
Все тесты можно разделить на следующие группы:
Группа | Макс. балл | Доп. ограничения | Комментарий |
0 | 0 | – | Тесты из условия. |
1 | 18 | $$$n, q, \sum k_i \leqslant 1000$$$ | |
2 | 14 | Нет запросов первого типа, а также $$$t_i = 1$$$. | |
3 | 10 | Нет запросов первого типа. | |
4 | 18 | $$$p_i = i - 1$$$ | |
5 | 18 | $$$p_i = \lfloor \frac{i}{2} \rfloor$$$ | |
6 | 22 | – |
4 41 2 21 1 3 32 3 10 72 3 2 3 42 1 2 4 31 3 12 1 2 3 4
10 6 10
В первом запросе караваны идут из городов с номерами $$$3$$$ и $$$4$$$ и нужно ограбить их в городе из третьей провинции. Это те же самые города с номерами $$$3$$$ и $$$4$$$, через каждый из которых пройдет по одному каравану. Поэтому разбойники ограбят караваны в третьем городе и получат $$$c_3 \cdot 1 = 10 \cdot 1 = 10$$$.
Во втором запросе караваны также идут из городов с номерами $$$3$$$ и $$$4$$$, но теперь нужно ограбить их в городе из первой провинции. В первой провинции находятся города $$$1$$$ и $$$2$$$, через каждый из которых пройдет два каравана. Среди них разбойники выбирают город $$$2$$$, потому что $$$c_2 > c_1$$$ и ответ на этот запрос равен $$$c_2 \cdot 2 = 3 \cdot 2 = 6$$$.
В третьем провинция для города $$$3$$$ изменяется на $$$1$$$.
В четвертом запросе караваны снова идут из городов с номерами $$$3$$$ и $$$4$$$, и нужно ограбить караваны в городе из первой провинции. То есть разбойники могут ограбить караваны в одном из городов с номерами $$$1, 2$$$ или $$$3$$$. Через города с номерами $$$1$$$ и $$$2$$$ пройдет два каравана, а через город $$$3$$$ только один. Разбойникам выгодно ограбить караваны в городе $$$3$$$ и получить $$$c_3 \cdot 1 = 10 \cdot 1 = 10$$$.