「BalkanOI 2023 Day2」Super Tree

题目描述

译自 BalkanOI 2023 Day2 T1「Super Tree」

给定一棵有 $n$ 个节点的有根树，节点用 $0, \ldots, n-1$ 的编号来标识。根节点的编号为 $0$。节点 $i\ (0\leq i\leq n-1)$ 被赋予一个整数 $a_{i}$。令 $f_{v}$ 为从节点 $v$ 到根节点的简单路径（包括 $v$ 和根节点本身）上所有 $a_{i}$ 的按位与（以下用 $\&$ 表示）的值。令树的能量为

$$\sum_{0 \leq u, v<n} f_{u} \cdot f_{v}$$

的值，令树的超能量为（注意范围的区别）

$$\sum_{0 \leq u<v<n} f_{u} \cdot f_{v}$$

的值。为了说明清楚，可以参考下面的样例解释。

我们说一个节点 $u$ 属于另一个节点 $v$ 的子树，如果 $v$ 在从节点 $u$ 到根节点的简单路径上。注意，一个节点 $x$ 的子树包括 $x$ 本身。

给定 $q$ 次更新。每次更新由两个整数 $v$ 和 $x$ 描述，要求你对节点 $v$ 的子树中的每个节点 $u$，令 $a_{u}=a_{u} \& x$。在每次更新后，你应该输出当前树的能量和超能量。

由于输出值可能很大，你只需要求出答案对 $10^9+7$ 取模的结果。

输入格式

第一行包含两个整数 $n$ 和 $q$。

第二行包含 $n-1$ 个整数 $p_{1}, p_{2}, \ldots, p_{n-1}$。$p_{i}\ (0\leq i\leq n-1)$ 是节点 $i$ 的父节点的编号，且满足 $0 \leq p_{i}<i$。

第三行包含 $n$ 个整数 $a_{0}, a_{1}, \ldots, a_{n-1}$。这些是赋给节点的值。

接下来的 $q$ 行，每行包含两个整数 $v$（$0 \leq v<n$）和 $x$。这些整数指定了各个更新。

输出格式

输出 $q+1$ 行。每行包含两个用空格分隔的整数。第一行，输出初始树的能量和超能量对 $10^9+7$ 取模的结果。在剩下的 $q$ 行中，第 $i\ (1\leq i\leq q)$ 行输出第 $i$ 次更新后的树的能量和超能量对 $10^9+7$ 取模的结果。

样例 1

输入

3 3
0 0
7 3 4
1 6
2 2
0 3

输出

196 61
169 50
81 14
25 6

解释

初始时，我们有

$$f_{0}=7, f_{1}=7 \& 3=3, f_{2}=7 \& 4=4$$

因此，树的能量等于

$$\begin{gathered} f_{0} \cdot f_{0}+f_{0} \cdot f_{1}+f_{0} \cdot f_{2}+f_{1} \cdot f_{0}+f_{1} \cdot f_{1}+f_{1} \cdot f_{2}+f_{2} \cdot f_{0}+f_{2} \cdot f_{1}+f_{2} \cdot f_{2}= \\ =7 \cdot 7+7 \cdot 3+7 \cdot 4+3 \cdot 7+3 \cdot 3+3 \cdot 4+4 \cdot 7+4 \cdot 3+4 \cdot 4=196 . \end{gathered}$$

树的超能量等于

$$f_{0} \cdot f_{1}+f_{0} \cdot f_{2}+f_{1} \cdot f_{2}=7 \cdot 3+7 \cdot 4+3 \cdot 4=61 . $$

第一次更新后：

$$\begin{gathered} a_{0}=7, a_{1}=3 \& 6=2, a_{2}=4 ; \\ f_{0}=7, f_{1}=2, f_{2}=4 . \end{gathered}$$

第二次更新后：

$$\begin{gathered} a_{0}=7, a_{1}=2, a_{2}=4 \& 2=0 \\ f_{0}=7, f_{1}=2, f_{2}=0 \end{gathered}$$

第三次更新后：

$$\begin{gathered} a_{0}=7 \& 3=3, a_{1}=2 \& 3=2, a_{2}=0 \& 3=0 \\ f_{0}=3, f_{1}=2, f_{2}=0 \end{gathered}$$

样例 2

输入

4 2
0 0 1
6 5 6 2
1 2
0 3

输出

256 84
144 36
16 4

解释

初始时，我们有

$$f_{0}=6, f_{1}=6 \& 5=4, f_{2}=6 \& 6=6, f_{3}=2 \& 5 \& 6=0 $$

第一次更新后：

$$\begin{gathered} a_{0}=6, a_{1}=5 \& 2=0, a_{2}=6, a_{3}=2 \& 2=2 ; \\ f_{0}=6, f_{1}=0, f_{2}=6, f_{3}=2 \& 0=0 \end{gathered}$$

第二次更新后：

$$\begin{gathered} a_{0}=6 \& 3=2, a_{1}=0 \& 3=0, a_{2}=6 \& 3=2, a_{3}=2 \& 3=2 ; \\ f_{0}=2, f_{1}=2 \& 0=0, f_{2}=2 \& 2=2, f_{3}=2 \& 0=0 \end{gathered}$$

（注：样例 2 原解释存在笔误，以上为修正后的正确状态，最终输出 $16=4^2$，$4=\frac{4^2 - (2^2+0^2+2^2+0^2)}{2}$ 符合结果）

样例 3

输入

7 3
0 0 1 1 2 2
7 6 5 7 3 4 2
4 4
3 3
2 1

输出

900 367
784 311
576 223
256 83

评分

对于给定的测试点，如果你的代码正确计算了所有的能量值，但是至少有一个超能量值计算错误，那么你的代码将获得该测试点 50% 的分数。

同样地，如果你的代码正确计算了所有的超能量值，但是至少有一个能量值计算错误，那么你的代码将获得该测试点 50% 的分数。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n, q \leq 10^6$
• $0 \leq a_{i}<2^{60}\ (0\leq i\leq n-1)$
• $0 \leq x<2^{60}$

详细子任务附加限制及分值如下表所示：

子任务编号	附加限制	分值
1	$n=3$	4
2	$n, q \leq 700$	7
3	$n, q \leq 5000$	13
4	$n \leq 10^5$，$p_{i}=i-1\ (1\leq i\leq n-1)$；$a_{i}, x<2^{20}\ (0\leq i\leq n-1)$	6
5	$p_{i}=i-1\ (1\leq i\leq n-1)$	7
6	$a_{i}, x<2^{20}\ (0\leq i\leq n-1)$	12
7	$n \leq 10^5$	14
8	$n \leq 5 \cdot 10^5$	11
9	无附加限制	26