H. Машина Голдберга 3
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дано полное корневое бинарное дерево, то есть корневое дерево, в котором у каждой вершины или $$$0$$$, или $$$2$$$ ребёнка. Корнем этого дерева является вершина $$$1$$$. Вершина без детей называется листом. У каждого листа есть значение голода, обозначим значение голода листа $$$v$$$ через $$$h_v$$$.

В каждой внутренней вершине дерева есть свой переключатель, указывающий на одного из сыновей этой вершины.

Дерево принимает печеньки. Перед запуском процесса вы можете выбрать начальное положение каждого переключателя для всех вершин независимо. Процесс устроен следующим образом:

  • Изначально в вершинах нет печенек.
  • Вы вставляете печеньки по одной в корневую вершину.
  • Пока печенька не спустилась до листа, она падает в ребёнка, на которого указывает переключатель в текущей вершине. Сам переключатель после этого изменяет своё состояние на противоположное, т. е. начинает указывать на другого ребёнка.
  • Вы перестаёте кормить машину печеньем, когда в каждом листе $$$v$$$ будет хотя бы $$$h_v$$$ печенек. В этом случае дерево считается накормленным.

Даны $$$q$$$ запросов. Каждый запрос меняет значение $$$h_v$$$ для какого-то листа $$$v$$$. Вам необходимо вывести $$$q + 1$$$ число, $$$i$$$-е из которых равно минимальному количеству печенек, необходимых для того, чтобы полностью накормить машину после первых $$$(i - 1)$$$ запросов, если перед запуском процесса вы можете выбрать начальное положение каждого переключателя независимо. Поскольку это количество может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

Обратите внимание, что между запросами вы можете менять начальное состояние переключателей. Однако сами запросы не являются независимыми: при ответе на $$$i$$$-й запрос нужно также учесть эффект от запросов $$$1, 2, \ldots, i - 1$$$.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1\le n < 200\,000$$$) — количество вершин в дереве.

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

Третья строка содержит $$$n$$$ целых чисел $$$h_1, h_2, \ldots, h_n$$$ ($$$0\le h_i\le 10^9$$$) — значения голода для вершин. Если вершина $$$i$$$ не является листом, то $$$h_i = 0$$$, и это значение не играет роли. Однако $$$h_i = 0$$$ также может выполняться, если $$$i$$$ — лист.

Четвёртая строка содержит одно целое число $$$q$$$ ($$$0\le q\le 200\,000$$$) — количество запросов.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$v$$$ и $$$x$$$ ($$$1\le v\le n$$$, $$$0\le x\le 10^9$$$), задающих очередной запрос: это запрос замены значения голода вершины $$$v$$$ на $$$x$$$.

Гарантируется, что заданное дерево является полным корневым бинарным деревом с корнем в вершине $$$1$$$. Также гарантируется, что во всех запросах вершина $$$v$$$ является листом.

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

Выведите $$$q + 1$$$ число, $$$i$$$-е из которых равно минимальному количеству печенек, необходимых для того, чтобы накормить машину после $$$(i - 1)$$$ запросов, взятое по модулю $$$998\,244\,353$$$.

Пример
Входные данные
5
1 1 2 2
0 0 0 0 0
5
3 1
4 1
5 1
3 4
4 1000000000
Выходные данные
0
1
2
3
7
7022585
Примечание

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

После первого запроса можно сделать так, чтобы изначально переключатель в вершине $$$1$$$ указывал на вершину $$$3$$$. Тогда достаточно вставить одну печеньку, она немедленно упадёт в вершину $$$3$$$.

После второго запроса можно сделать так, чтобы изначально переключатель в вершине $$$1$$$ указывал на $$$3$$$, а переключатель в вершине $$$2$$$ — на вершину $$$4$$$. Первая печенька упадёт в вершину $$$3$$$ и изменит состояние переключателя в вершине $$$1$$$: теперь он будет указывать на $$$2$$$. Вторая печенька пройдёт по пути $$$1 \to 2 \to 4$$$.

После третьего запроса можно сделать так, чтобы изначально переключатель в вершине $$$1$$$ указывал на $$$2$$$, а переключатель в вершине $$$2$$$ — на вершину $$$4$$$. Тогда три печеньки пройдут по путям $$$1 \to 2 \to 4$$$, $$$1 \to 3$$$, $$$1 \to 2 \to 5$$$.

После четвёртого запроса можно сделать так, чтобы изначально переключатель в вершине $$$1$$$ указывал на $$$3$$$. Вне зависимости от исходного положения переключателя в вершине $$$2$$$, после того как мы вставим семь печенюшек в дерево, четыре из них окажутся в листе $$$3$$$, а в каждом из листьев $$$4$$$ и $$$5$$$ окажется по одной или две печеньки (обратите внимание, что превышать величины голода разрешается).

После пятого запроса ответ равен $$$3\,999\,999\,997$$$. Не забудьте вывести ответ по модулю $$$998\,244\,353$$$.