CF1863H Goldberg Machine 3

有一棵完全二叉树，也就是说，这是一棵有根树，每个结点要么有 $0$ 个子结点，要么有 $2$ 个子结点。树的根为结点 $1$。没有子结点的结点称为叶子结点。每个叶子结点有一个饥饿值，我们用 $h_v$ 表示叶子 $v$ 的饥饿值。 树中的每个内部结点都有一个选择器，指向该结点的某一个子结点。 这棵树可以接受饼干。在开始操作之前，你可以单独选择每个选择器的初始状态。操作过程如下： - 初始时，所有结点中都没有饼干。 - 你将饼干一个接一个地放入根结点。 - 只要饼干还没有到达叶子结点，它就会按照当前结点选择器指向的子结点继续下落。此时，该选择器的状态会切换到相反的状态，即开始指向该结点的另一个子结点。 - 当每个叶子 $v$ 中至少有 $h_v$ 个饼干时，你就停止投放饼干。此时我们称这棵树已经被“填满”。 你有 $q$ 次操作。每次操作会改变某个叶子结点 $v$ 的饥饿值 $h_v$。你需要输出 $q+1$ 个数，第 $i$ 个数表示在进行了前 $i-1$ 次操作后，若你可以任意选择每个选择器的初始状态，最少需要投放多少个饼干才能填满这棵树。由于答案可能很大，请输出对 $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$ 次操作后，最少需要投放多少个饼干才能填满这棵树，结果对 $998\,244\,353$ 取模。

考虑样例。在没有任何操作前，所有饥饿值都为零，因此不需要投放任何饼干。 第一次操作后，我们可以将结点 $1$ 的选择器指向结点 $3$，这样第一个饼干会直接落到 $3$。 第二次操作后，我们将结点 $1$ 的选择器指向结点 $3$，结点 $2$ 的选择器指向结点 $4$。第一个饼干会落到 $3$ 并切换结点 $1$ 的选择器状态，此时它指向 $2$。第二个饼干会经过 $1\to 2\to 4$。 第三次操作后，我们将结点 $1$ 的选择器指向 $2$，结点 $2$ 的选择器指向 $4$。这样三个饼干会分别落到 $1\to 2\to 4$，$1\to 3$，$1\to 2\to 5$。 第四次操作后，我们将结点 $1$ 的选择器指向 $3$。无论结点 $2$ 的选择器初始状态如何，投放七个饼干后，$3$ 号叶子会有四个饼干，$4$ 和 $5$ 号叶子会分别有一到两个饼干（注意允许超过饥饿值）。 第五次操作的答案是 $3\,999\,999\,997$。不要忘记输出对 $998\,244\,353$ 取模的结果。 由 ChatGPT 4.1 翻译