#P17788. Goldberg Machine 3

Goldberg Machine 3

CF1863H

题目描述

有一棵完全二叉树,也就是说,这是一棵有根树,每个结点要么有 00 个子结点,要么有 22 个子结点。树的根为结点 11。没有子结点的结点称为叶子结点。每个叶子结点有一个饥饿值,我们用 hvh_v 表示叶子 vv 的饥饿值。

树中的每个内部结点都有一个选择器,指向该结点的某一个子结点。

这棵树可以接受饼干。在开始操作之前,你可以单独选择每个选择器的初始状态。操作过程如下:

  • 初始时,所有结点中都没有饼干。
  • 你将饼干一个接一个地放入根结点。
  • 只要饼干还没有到达叶子结点,它就会按照当前结点选择器指向的子结点继续下落。此时,该选择器的状态会切换到相反的状态,即开始指向该结点的另一个子结点。
  • 当每个叶子 vv 中至少有 hvh_v 个饼干时,你就停止投放饼干。此时我们称这棵树已经被“填满”。

你有 qq 次操作。每次操作会改变某个叶子结点 vv 的饥饿值 hvh_v。你需要输出 q+1q+1 个数,第 ii 个数表示在进行了前 i−1i-1 次操作后,若你可以任意选择每个选择器的初始状态,最少需要投放多少个饼干才能填满这棵树。由于答案可能很大,请输出对 998 244 353998\,244\,353 取模后的结果。

请注意,你可以在每次操作后独立地选择所有选择器的初始状态。然而,操作之间是相关的:在回答第 ii 次操作时,你还需要考虑前 1,2,…,i−11,2,\ldots,i-1 次操作的影响。

输入格式

第一行包含一个整数 nn(1≤n<200 0001\le n < 200\,000),表示树中结点的数量。

第二行包含 n−1n-1 个整数 p2,p3,…,pnp_2, p_3, \ldots, p_n(1≤pi<i1\le p_i < i),表示结点 ii 的父结点为 pip_i。

第三行包含 nn 个整数 h1,h2,…,hnh_1, h_2, \ldots, h_n(0≤hi≤1090\le h_i\le 10^9),表示各结点的饥饿值。如果结点 ii 不是叶子结点,则 hi=0h_i=0,这个值无实际意义。当然,如果 ii 是叶子结点,也可能有 hi=0h_i=0。

第四行包含一个整数 qq(0≤q≤200 0000\le q\le 200\,000),表示操作次数。

接下来的 qq 行,每行包含两个整数 vv 和 xx(1≤v≤n1\le v\le n,0≤x≤1090\le x\le 10^9),表示将结点 vv 的饥饿值设置为 xx。

保证输入中的树是以结点 11 为根的满二叉树。保证每次操作中的 vv 都是叶子结点。

输出格式

输出 q+1q+1 个整数,第 ii 个表示在进行了前 i−1i-1 次操作后,最少需要投放多少个饼干才能填满这棵树,结果对 998 244 353998\,244\,353 取模。

输入输出样例 #1

输入 #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

说明/提示

考虑样例。在没有任何操作前,所有饥饿值都为零,因此不需要投放任何饼干。

第一次操作后,我们可以将结点 11 的选择器指向结点 33,这样第一个饼干会直接落到 33。

第二次操作后,我们将结点 11 的选择器指向结点 33,结点 22 的选择器指向结点 44。第一个饼干会落到 33 并切换结点 11 的选择器状态,此时它指向 22。第二个饼干会经过 1→2→41\to 2\to 4。

第三次操作后,我们将结点 11 的选择器指向 22,结点 22 的选择器指向 44。这样三个饼干会分别落到 1→2→41\to 2\to 4,1→31\to 3,1→2→51\to 2\to 5。

第四次操作后,我们将结点 11 的选择器指向 33。无论结点 22 的选择器初始状态如何,投放七个饼干后,33 号叶子会有四个饼干,44 和 55 号叶子会分别有一到两个饼干(注意允许超过饥饿值)。

第五次操作的答案是 3 999 999 9973\,999\,999\,997。不要忘记输出对 998 244 353998\,244\,353 取模的结果。