G. Самая удивительная вершина
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано корневое дерево с $$$n$$$ вершинами. Вершины нумеруются от $$$1$$$ до $$$n$$$; корнем является вершина $$$1$$$.

С каждой вершиной связаны два числа: $$$a_i$$$ и $$$b_i$$$. Обозначим множество всех предков $$$v$$$ (включая саму вершину $$$v$$$) как $$$R(v)$$$. Обозначим крутость вершины $$$v$$$ как

$$$$$$\left| \sum_{w \in R(v)} a_w\right| \cdot \left|\sum_{w \in R(v)} b_w\right|,$$$$$$

где $$$|x|$$$ обозначает абсолютную величину $$$x$$$.

Нужно выполнить $$$q$$$ запросов двух типов:

  • 1 v x — увеличить $$$a_v$$$ на положительное число $$$x$$$.
  • 2 v — найти максимальную крутость в поддереве вершины $$$v$$$.
Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n \leq 2\cdot 10^5, 1 \leq q \leq 10^5$$$) — количество вершин в дереве и количество запросов соответственно.

Вторая строка содержит $$$n - 1$$$ целых чисел $$$p_2, p_3, \dots, p_n$$$ ($$$1 \leq p_i < i$$$), где $$$p_i$$$ значит, что есть ребро между вершинами $$$i$$$ и $$$p_i$$$.

Третья строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-5000 \leq a_i \leq 5000$$$) — начальные значения $$$a_i$$$ для каждой вершины.

Четвертая строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$-5000 \leq b_i \leq 5000$$$) — значения $$$b_i$$$ для каждой вершины.

Каждая из следующих $$$q$$$ строк описывает запрос. Каждая из них имеет одну из двух форм:

  • 1 v x  ($$$1 \leq v \leq n$$$, $$$1\leq x \leq 5000$$$).
  • 2 v  ($$$1 \leq v \leq n$$$).
Выходные данные

Для каждого запроса второго типа нужно в отдельной строке вывести максимальную крутость в соответствующем поддереве.

Пример
Входные данные
5 6
1 1 2 2
10 -3 -7 -3 -10
10 3 9 3 6
2 1
2 2
1 2 6
2 1
1 2 5
2 1
Выходные данные
100
91
169
240
Примечание

Начальная крутость вершин равна $$$[100, 91, 57, 64, 57]$$$. Самая крутая вершина в поддереве вершины $$$1$$$ (первый запрос) — это вершина $$$1$$$, а самая крутая вершина в поддереве вершины $$$2$$$ (второй запрос) — это вершина $$$2$$$.

После первого обновления (третий запрос), крутость вершин станет равна $$$[100, 169, 57, 160, 57]$$$, и поэтому самая крутая вершина во всем дереве (четвертый запрос) теперь $$$2$$$.

После второго обновления (пятый запрос), крутость вершин станет равна $$$[100, 234, 57, 240, 152]$$$, поэтому самая крутая вершина (шестой запрос) теперь $$$4$$$.