存在一棵完全有根二叉树,即每个顶点都有 $$$0$$$ 或 $$$2$$$ 子节点的有根树。树的根是顶点$$$1$$$。没有子节点的节点称为叶子。每片叶子都有一个饥饿值,我们用$$$h_v$$$表示叶子$$$v$$$的饥饿值。
树的每个内部顶点都有一个指向该顶点的子节点之一的选择器。
此树接受 cookie。在启动该过程之前,您可以单独选择每个选择器的初始状态。流程如下:
- 最初顶点中没有 cookie。
- 您将 cookie 逐一插入到根目录中。
- 只要 cookie 不在叶子中,它就会落入当前顶点中选择器定义的子节点。然后,该选择器将其状态更改为相反的状态,即。 e.它开始指向顶点的另一个子节点。
- 当每个叶子 $$$v$$$ 中至少有 $$$h_v$$$ cookie 时,您将停止插入 cookie。在这种情况下,我们说树已填满。
您有 $$$q$$$ 查询。每个查询都会更改某些叶子 $$$v$$$ 的 $$$h_v$$$ 值。您需要打印 $$$q + 1$$$ 数字,如果您可以为每个选择器选择任何初始状态,则其中的 $$$i$$$ 是在 $$$(i - 1)$$$ 更新后填充机器所需的最小 cookie 数量。由于这些数字可能非常大,因此请打印对 $$$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$$$ 并且该值无关紧要。然而,如果 $$$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)$$$ 更新后填充机器所需的最小 cookie 数量,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
5 1 1 2 2 0 0 0 0 0 5 3 1 4 1 5 1 3 4 4 1000000000
输出 #1
0 1 2 3 7 7022585
注意
考虑这个例子。在进行任何查询之前,不需要插入 cookie,因为所有饥饿值为零都可以轻松满足。
在第一次查询后,我们可以选择顶点$$$1$$$中指向顶点$$$3$$$的选择器。那么一块 cookie 将立即下降到 $$$3$$$。
在第二个查询之后,我们选择顶点 $$$1$$$ 中指向顶点 $$$3$$$ 的选择器,以及顶点 $$$2$$$ 中指向顶点 $$$4$$$ 的选择器。第一个 cookie 将下降到 $$$3$$$ 并更改顶点 $$$1$$$ 中选择器的状态:现在它指向 $$$2$$$。第二个 cookie 将通过路径 $$$1 \to 2 \to 4$$$。
第三次查询后,我们选择顶点$$$1$$$中指向顶点$$$2$$$的选择器和顶点$$$2$$$中指向顶点$$$4$$$的选择器。然后,这三个 cookie 将通过路径 $$$1 \to 2 \to 4$$$、$$$1 \to 3$$$、$$$1 \to 2 \to 5$$$ 下降。
第四次查询后,我们选择顶点$$$1$$$中指向顶点$$$3$$$的选择器。无论顶点$$$2$$$中选择器的初始状态如何,插入7个cookie后,其中4个将在叶子$$$3$$$中,并且叶子$$$4$$$和$$$5$$$中各将有1个或2个cookie(注意超过饥饿值是允许的)。
第五次查询后的答案是$$$3\,999\,999\,997$$$。不要忘记打印答案模 $$$998\,244\,353$$$。