Караваны и Провинции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Далекая страна содержит $$$n$$$ городов, соединенных $$$n - 1$$$ дорогами, при этом из любого города можно добраться до любого другого по дорогам страны.

Известно, что каждый город относится ровно к одной провинции. Город $$$v$$$ относится к провинции $$$t_v$$$. Обратите внимание, что конкретная провинция может являться любым подмножеством городов, и возможно из одного города провинции нельзя добраться до другого этой же провинции, проходя только через города этой провинции. Столицей является город номер $$$1$$$.

Банда разбойников собирается грабить караваны, которые будут идти через города страны. У каждого города есть коэффициент того, насколько удобно в нем грабить. В городе $$$v$$$ он равен $$$c_v$$$.

Вам приходят запросы двух типов:

  1. Изменить провинцию, к которой относится город $$$v$$$, на $$$t_{new}$$$

  2. В $$$k$$$ городах с номерами $$$a_1, a_2, \ldots, a_k$$$ появляется по одному каравану, которые идут в столицу (город с номером 1) по кратчайшему пути. Разбойники выбирают один город, который находится в провинции $$$t$$$, после чего грабят все караваны, которые пройдут через этот город. Если разбойники ограбят караваны в городе с номером $$$v$$$, то они получат $$$c_v \cdot num_v$$$, где $$$c_v$$$ — коэффициент города $$$v$$$, а $$$num_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$$$) — тип запроса.

  1. Если $$$x_i = 1$$$, то далее идет два целых числа $$$v$$$ и $$$t_{new}$$$ ($$$1 \le v, t_{new} \le n$$$) — номер города, у которого меняется провинция, и номер его новой провинции.

  2. Если $$$x_i = 2$$$, то далее идут целые числа $$$t$$$ и $$$k$$$, и $$$k$$$ целых чисел $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le t, k, a_i \le n$$$) — номер провинции, в городе которой можно грабить; количество городов, из которых выходят караваны; и номера городов, из которых входят караваны. Гарантируется, что в одном запросе все $$$a_i$$$ различны. Также гарантируется, что сумма $$$k$$$ по всем запросам второго типа не превышает $$$200\,000$$$.

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

На каждый запрос второго типа выведите одно число — максимальное число, которое разбойники смогут получить. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен $$$0$$$.

Система оценки

Все тесты можно разделить на следующие группы:

ГруппаМакс. баллДоп. ограниченияКомментарий
00Тесты из условия.
118$$$n, q, \sum k_i \leqslant 1000$$$
214Нет запросов первого типа, а также $$$t_i = 1$$$.
310Нет запросов первого типа.
418$$$p_i = i - 1$$$
518$$$p_i = \lfloor \frac{i}{2} \rfloor$$$
622

Пример

Входные данные
4 4
1 2 2
1 1 3 3
2 3 10 7
2 3 2 3 4
2 1 2 4 3
1 3 1
2 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$$$.