← 返回题目列表

Codeforces · 1863/H

H. 戈德堡机 3

中文机器翻译题面 查看原题

存在一棵完全有根二叉树,即每个顶点都有 $$$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$$$。