#P17788. Goldberg Machine 3
Goldberg Machine 3
CF1863H
题目描述
有一棵完全二叉树,也就是说,这是一棵有根树,每个结点要么有 个子结点,要么有 个子结点。树的根为结点 。没有子结点的结点称为叶子结点。每个叶子结点有一个饥饿值,我们用 表示叶子 的饥饿值。
树中的每个内部结点都有一个选择器,指向该结点的某一个子结点。
这棵树可以接受饼干。在开始操作之前,你可以单独选择每个选择器的初始状态。操作过程如下:
- 初始时,所有结点中都没有饼干。
- 你将饼干一个接一个地放入根结点。
- 只要饼干还没有到达叶子结点,它就会按照当前结点选择器指向的子结点继续下落。此时,该选择器的状态会切换到相反的状态,即开始指向该结点的另一个子结点。
- 当每个叶子 中至少有 个饼干时,你就停止投放饼干。此时我们称这棵树已经被“填满”。
你有 次操作。每次操作会改变某个叶子结点 的饥饿值 。你需要输出 个数,第 个数表示在进行了前 次操作后,若你可以任意选择每个选择器的初始状态,最少需要投放多少个饼干才能填满这棵树。由于答案可能很大,请输出对 取模后的结果。
请注意,你可以在每次操作后独立地选择所有选择器的初始状态。然而,操作之间是相关的:在回答第 次操作时,你还需要考虑前 次操作的影响。
输入格式
第一行包含一个整数 (),表示树中结点的数量。
第二行包含 个整数 (),表示结点 的父结点为 。
第三行包含 个整数 (),表示各结点的饥饿值。如果结点 不是叶子结点,则 ,这个值无实际意义。当然,如果 是叶子结点,也可能有 。
第四行包含一个整数 (),表示操作次数。
接下来的 行,每行包含两个整数 和 (,),表示将结点 的饥饿值设置为 。
保证输入中的树是以结点 为根的满二叉树。保证每次操作中的 都是叶子结点。
输出格式
输出 个整数,第 个表示在进行了前 次操作后,最少需要投放多少个饼干才能填满这棵树,结果对 取模。
输入输出样例 #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
说明/提示
考虑样例。在没有任何操作前,所有饥饿值都为零,因此不需要投放任何饼干。
第一次操作后,我们可以将结点 的选择器指向结点 ,这样第一个饼干会直接落到 。
第二次操作后,我们将结点 的选择器指向结点 ,结点 的选择器指向结点 。第一个饼干会落到 并切换结点 的选择器状态,此时它指向 。第二个饼干会经过 。
第三次操作后,我们将结点 的选择器指向 ,结点 的选择器指向 。这样三个饼干会分别落到 ,,。
第四次操作后,我们将结点 的选择器指向 。无论结点 的选择器初始状态如何,投放七个饼干后, 号叶子会有四个饼干, 和 号叶子会分别有一到两个饼干(注意允许超过饥饿值)。
第五次操作的答案是 。不要忘记输出对 取模的结果。