310639: CF1863H. Goldberg Machine 3
Description
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$.
InputThe 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.
OutputOutput $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$.
ExampleInput5 1 1 2 2 0 0 0 0 0 5 3 1 4 1 5 1 3 4 4 1000000000Output
0 1 2 3 7 7022585Note
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$.
Output
题目描述了一个完全根二叉树，即每个节点要么没有子节点，要么有两个子节点的树。树的根节点是1号节点。没有子节点的节点称为叶子。每个叶子都有一个饥饿值，用$h_v$表示叶子$v$的饥饿值。
树中的每个内部节点都有一个选择器，指向该节点的某个子节点。
这棵树可以接受饼干。在启动过程之前，你可以为每个选择器单独选择初始状态。过程如下：
- 初始时，节点中没有饼干。
- 你一个接一个地将饼干插入根节点。
- 只要饼干不在叶子上，它就会落到当前节点选择器指向的子节点。然后，这个选择器会改变状态，指向该节点的另一个子节点。
- 当每个叶子$v$至少有$h_v$个饼干时，停止插入饼干。在这种情况下，我们说这棵树被填满了。
你有$q$个查询。每个查询都会改变某个叶子$v$的$h_v$值。你需要输出$q+1$个数，第$i$个数是在进行了$i-1$次更新后，如果你可以为每个选择器选择任意初始状态，那么填满机器所需的最少饼干数。由于这些数字可能非常大，所以请以模$998,244,353$的形式打印答案。
请注意，你可以在查询之间独立地为所有选择器选择初始状态。但是，查询本身并不是独立的：在回答第$i$个查询时，你也应该考虑查询1、2、...、$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$，这个值是无关紧要的。但是，即使$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$是叶子。
**输出数据格式：**
输出$q+1$个整数，第$i$个数是在进行了$i-1$次更新后，填满机器所需的最少饼干数，模$998,244,353$。**题目大意：** 题目描述了一个完全根二叉树，即每个节点要么没有子节点，要么有两个子节点的树。树的根节点是1号节点。没有子节点的节点称为叶子。每个叶子都有一个饥饿值，用$h_v$表示叶子$v$的饥饿值。 树中的每个内部节点都有一个选择器，指向该节点的某个子节点。 这棵树可以接受饼干。在启动过程之前，你可以为每个选择器单独选择初始状态。过程如下： - 初始时，节点中没有饼干。 - 你一个接一个地将饼干插入根节点。 - 只要饼干不在叶子上，它就会落到当前节点选择器指向的子节点。然后，这个选择器会改变状态，指向该节点的另一个子节点。 - 当每个叶子$v$至少有$h_v$个饼干时，停止插入饼干。在这种情况下，我们说这棵树被填满了。 你有$q$个查询。每个查询都会改变某个叶子$v$的$h_v$值。你需要输出$q+1$个数，第$i$个数是在进行了$i-1$次更新后，如果你可以为每个选择器选择任意初始状态，那么填满机器所需的最少饼干数。由于这些数字可能非常大，所以请以模$998,244,353$的形式打印答案。 请注意，你可以在查询之间独立地为所有选择器选择初始状态。但是，查询本身并不是独立的：在回答第$i$个查询时，你也应该考虑查询1、2、...、$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$，这个值是无关紧要的。但是，即使$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$是叶子。 **输出数据格式：** 输出$q+1$个整数，第$i$个数是在进行了$i-1$次更新后，填满机器所需的最少饼干数，模$998,244,353$。