Goldberg Machine 3
Contest: Pinely Round 2 (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: dp, trees

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$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1\le n < 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 < 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.

Output format:
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$$$.

Constraints:
Time limit: 8.0 s
Memory limit: 1024.0 MB

Note:
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$$$.

Example input:
5
1 1 2 2
0 0 0 0 0
5
3 1
4 1
5 1
3 4
4 1000000000

Example output:
0
1
2
3
7
7022585

Editorial:
Let's consider a dynamic programming approach: for leaves, set $$$dp_v = a_v$$$, and for an internal vertex $$$v$$$ with children $$$u$$$ and $$$w$$$, set $$$dp_v = 2 \max(dp_u, dp_w)−[dp_u \neq dp_w]$$$ we use an indicator notation $$$[\ldots]$$$.
Let $$$d_v = dp_v - 1$$$, then the update becomes $$$d_v = 2 \max(d_u, d_w) + [d_u = d_w]$$$. Let $$$h_v$$$ denote the distance from the root to $$$v$$$, and $$$D_v = d_v \cdot 2^{h_v}$$$. Then $$$D_v = \max(D_u, D_w) + 2^{h_v} [D_u = D_w]$$$.
Notice that the binary representation of $$$D_v$$$ contains at most $$$\log_2 A + \log_2 n$$$ ones ($$$A = \max a_i$$$). This can be easily proven by induction: suppose the minimum size of a tree that can result in $$$D_v$$$ having $$$k$$$ ones is $$$f(k)$$$. Then, $$$f(k) = 1$$$ when $$$k \le \log_2 A$$$, and $$$f(k) \ge 2f(k - 1)$$$ otherwise, since $$$D_v$$$ must be constructed from equal $$$Du$$$ and $$$Dw$$$ from independent subtrees.
We'll maintain a set $$$S$$$ of pairs $$$(v, D)$$$, where $$$D$$$ is a lower bound on $$$D_v$$$. Initially, put pairs $$$(v,(a_v - 1)\cdot 2^{h_v})$$$ into $$$S$$$ for all leaves with $$$a_v > 0$$$, and if there are $$$(v, D)$$$ and $$$(u, D)$$$ in $$$S$$$ ($$$v \neq u$$$), put $$$(w, D + 2^{h_w})$$$ into $$$S$$$, where $$$w = \text{lca}(v, u)$$$. The answer is $$$1 +$$$ the maximum $$$D$$$ among all pairs in $$$S$$$ (if $$$S$$$ is empty, the answer is obviously $$$0$$$).
Start with an empty $$$S$$$ and add all the leaves to it. A new pair $$$(v, D)$$$ can create at most one new lca with pairs $$$(u, D)$$$, and at most one new pair $$$(w, D + 2^k)$$$, where $$$k$$$ is necessarily a new bit. The process of creating new pairs continues, but it will finish in $$$O(\log A + \log n)$$$ iterations since there cannot be more bits. Different $$$D$$$ values can be stored in a trie based on bit positions from most significant to least significant (or by some hashing), and vertex sets in the trie nodes can be stored in the order of entry time.
To change $$$a_v$$$, remove the old pair from $$$S$$$ (similarly to adding) and add the new one. All together requires $$$O(\log n \cdot (\log A + \log n))$$$ operations.