CF1863H.Goldberg Machine 3

There is a complete rooted binary tree, that is, a rooted tree in which each vertex has either $0$ or $2$ children. The root of the tree is vertex $1$. A node without children is called a leaf. Each leaf has a hunger value, we denote the hunger value of leaf $v$ by $h_v$.

Each inner vertex of the tree has a selector pointing to one of the children of the vertex.

This tree accepts cookies. Before launching the process you can choose the initial state of each selector individually. The process is as follows:

• Initially there are no cookies in vertices.
• You insert cookies into the root one by one.
• As long as the cookie is not in a leaf, it falls to the child defined by the selector in the current vertex. This selector then changes its state to the opposite one, i. e. it starts pointing to the other child of the vertex.
• You stop inserting cookies when each leaf $v$ has at least $h_v$ cookies in it. In this case, we say that the tree is filled up.

You have $q$ queries. Each query changes the value of $h_v$ for some leaf $v$. You need to print $q + 1$ numbers, the $i$-th of them being the minimum number of cookies required to fill up the machine after $(i - 1)$ updates if you can pick any initial state for every selector. Since these numbers may be very large, print the answers modulo $998\,244\,353$.

Please note that you can choose the initial state of all selectors independently between queries. However, the queries themselves are not independent: when answering the $i$-th query, you should also consider the effect of queries $1, 2, \ldots, i - 1$.

存在一棵完全有根二叉树，即一棵有根树，其中每个顶点的子节点数为 $0$ 或 $2$。该树的根节点为顶点 $1$。没有子节点的节点称为叶节点。每个叶节点 $v$ 具有一个“饥饿值”，记作 $h_v$。

树中每个内部顶点均配有一个选择器（selector），该选择器指向该顶点的两个子节点之一。

该树可接收饼干（cookies）。在启动处理过程前，你可以独立地为每个选择器任意设定其初始状态。处理过程如下：

• 初始时，所有顶点中均无饼干；
• 你逐个将饼干插入根节点；
• 只要当前饼干尚未到达叶节点，它就会沿当前顶点的选择器所指向的子节点下落；随后该选择器立即翻转其状态（即改为指向该顶点的另一个子节点）；
• 当每个叶节点 $v$ 均至少拥有 $h_v$ 个饼干时，停止插入饼干。此时称该树已被“填满”。

你将收到 $q$ 个查询，每个查询会修改某个叶节点 $v$ 的饥饿值 $h_v$。你需要输出 $q + 1$ 个整数：其中第 $i$ 个数表示在执行了前 $(i - 1)$ 次更新后，为使树被填满所需投入的最少饼干总数（你可在每次更新后重新自由选择所有选择器的初始状态）。由于答案可能极大，请对 $998\,244\,353$ 取模后输出。

请注意：你可以在不同查询之间独立地为所有选择器重新设定初始状态。但这些查询本身并非相互独立：在回答第 $i$ 个查询时，必须同时考虑第 $1, 2, \ldots, i - 1$ 个查询所带来的全部修改效果。

The first line contains a single integer $n$ ($1\le n \lt 200\,000$) — the number of vertices in the tree.

The second line contains $n - 1$ integers $p_2, p_3, \ldots, p_n$ ($1\le p_i \lt i$), meaning that the parent of vertex $i$ is $p_i$.

The third line contains $n$ integers $h_1, h_2, \ldots, h_n$ ($0\le h_i\le 10^9$) — the hunger values of vertices. If vertex $i$ is not a leaf, then $h_i = 0$ and this value is irrelevant. However, $h_i = 0$ may also hold if $i$ is a leaf.

The fourth line contains a single integer $q$ ($0\le q\le 200\,000$) — the number of queries.

Each of the next $q$ lines contains two integers $v$ and $x$ ($1\le v\le n$, $0\le x\le 10^9$), meaning that the hunger value of vertex $v$ is set to $x$.

It is guaranteed that the tree in the input is a full binary tree rooted at vertex $1$. It is also guaranteed that in each query $v$ is a leaf.

第一行包含一个整数 $n$（$1\le n \lt 200\,000$），表示树中顶点的数量。

第二行包含 $n - 1$ 个整数 $p_2, p_3, \ldots, p_n$（$1\le p_i \lt i$），表示顶点 $i$ 的父节点为 $p_i$。

第三行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$（$0\le h_i\le 10^9$），表示各顶点的饥饿值。若顶点 $i$ 不是叶子节点，则 $h_i = 0$，该值无关紧要；但若 $i$ 是叶子节点，也可能有 $h_i = 0$。

第四行包含一个整数 $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$ 均为叶子节点。

Output $q + 1$ integers, $i$-th of them being the minimum number of cookies needed to fill up the machine after $(i - 1)$ updates, modulo $998\,244\,353$.

输出 $q + 1$ 个整数，其中第 $i$ 个整数表示在执行 $(i - 1)$ 次更新后，填满该机器所需的最少饼干数量，对 $998\,244\,353$ 取模。

Consider the example. Before any queries are made, no cookies need to be inserted, since all hunger values of zero are trivially satisfied.

After the first query, we can choose the selector in vertex $1$ pointing to vertex $3$. Then one cookie will immediately descend to $3$.

After the second query, we choose the selector in vertex $1$ pointing to vertex $3$ and the selector in vertex $2$ pointing to vertex $4$. The first cookie will drop down to $3$ and change the state of the selector in vertex $1$: now it is pointing to $2$. The second cookie will go via the path $1 \to 2 \to 4$.

After the third query, we choose the selector in vertex $1$ pointing to vertex $2$ and the selector in vertex $2$ pointing to vertex $4$. Then the three cookies will descend via the paths $1 \to 2 \to 4$, $1 \to 3$, $1 \to 2 \to 5$.

After the fourth query, we choose the selector in vertex $1$ pointing to vertex $3$. Regardless of the initial state of the selector in vertex $2$, after seven cookies are inserted, four of them will be in leaf $3$, and one or two cookies will be in each of the leaves $4$ and $5$ (note that exceeding the hunger value is allowed).

The answer after the fifth query is $3\,999\,999\,997$. Do not forget to print the answer modulo $998\,244\,353$.

考虑该示例。在执行任何查询之前，无需插入饼干，因为所有饥饿值为零的情况均平凡地满足。

第一次查询后，我们可以选择顶点 $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$ 取模后输出。