#5760. 「ROI 2026 Day2」优美染色 - 8

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 ROI 2026 Day2 T4. Хорошие раскраски – 8

Ildar 决定投身于抽象艺术创作。他选择了一棵拥有 $n$ 个顶点的有根树作为画作的基础：这是一个无环连通图，其中 $1$ 号顶点被指定为根。根节点没有父节点，而对于任何其他顶点 $u \ge 2$，从 $u$ 到根的路径上的第一个顶点被称为顶点 $u$ 的父节点，记作 $p_u$。以顶点 $v$ 为父节点的顶点被称为 $v$ 的子节点。如果没有子节点的顶点，则被称为叶子节点。题目保证根节点至少有两个子节点。

我们对这棵树进行深度优先搜索（DFS）：首先访问根节点，然后依次递归地以相同方式访问其子节点的子树。树中的顶点按照这种深度优先搜索的顺序进行编号。因此，对于每个 $1$ 到 $n$ 之间的 $i$，顶点 $i$ 的子树中的所有顶点编号构成了一组连续的整数。

假设树中有 $m$ 个叶子节点。Ildar 将这些叶子节点的编号按升序排列，得到序列 $l_1 < l_2 < \dots < l_m$。他将所有形式为 $(l_j, l_{j + 1})$ 的叶子节点对用边连接起来，并连接顶点 $l_m$ 和 $l_1$。图中新增加的这个环 $l_1 \to l_2 \to \dots \to l_m \to l_1$ 被称为外层循环。

Ildar 在平面上绘制了得到的图：他将外层循环画成一个圆，叶子节点 $l_1, l_2, \dots, l_m$ 沿圆周按逆时针方向排列，相邻顶点之间的圆弧表示外层循环的边。树的其他顶点被描绘为圆内的不同点。树的边由顶点之间的线段表示，且顶点和边的布局使得所有表示边的线段在内部没有公共交点。下图展示了一个树的绘图示例。

图片下载失败URL：https://img.loj.ac.cn/2026/06/24/4532f2f16f9a0.svg

在 Ildar 的画作中，外层循环圆圈内部的平面部分被图的边划分为 $m$ 个区域。我们将这些区域称为面。若两个不同的面拥有一条公共边，则称它们是相邻的。例如，在上图中共有 $5$ 个面，分别记为 $\Gamma_1, \Gamma_2, \Gamma_3, \Gamma_4$ 和 $\Gamma_5$。

图片下载失败URL：https://img.loj.ac.cn/2026/06/24/943c9b0a6cbd9.svg

在上图中，相邻的面有 $(\Gamma_1, \Gamma_2)$，$(\Gamma_1, \Gamma_5)$，$(\Gamma_2, \Gamma_3)$，$(\Gamma_2, \Gamma_4)$，$(\Gamma_2, \Gamma_5)$，$(\Gamma_3, \Gamma_4)$ 和 $(\Gamma_4, \Gamma_5)$。

为了完成画作，Ildar 计划用 $k$ 种颜色之一为每个面着色。如果相邻的面涂有不同的颜色，则称该染色方案是正确的。Ildar 将其画作的潜力值定义为正确染色方案总数对 $10^9+7$ 取模后的余数。

在评估了原始画作的潜力值后，Ildar 对图中的边执行了 $q$ 次操作。第 $i$ 次操作由一个数字 $v_i$ 指定，针对连接顶点 $v_i$ 和 $p_{v_i}$ 的树边。若该边当前存在于图中，则 Ildar 将其从画中删除；若该边当前不存在，则将其重新画出。每次修改后，图中的面集合可能会发生变化：删除一条边时两个面可能会合并，而画出一条边时一个面可能会分裂成两个。例如，若在上图中删除边 $8-9$，则面 $\Gamma_4$ 和 $\Gamma_5$ 将合并为一个面 $\Gamma_{4+5}$。

图片下载失败URL：https://img.loj.ac.cn/2026/06/24/12b32a64eaa25.svg

此时，图中相邻的面变为 $(\Gamma_1, \Gamma_2)$，$(\Gamma_1, \Gamma_{4+5})$，$(\Gamma_2, \Gamma_3)$，$(\Gamma_2, \Gamma_{4+5})$ 和 $(\Gamma_3, \Gamma_{4+5})$。

在执行每次操作后，都需要重新确定画作的潜力值：即使用不超过 $k$ 种颜色对各面进行正确染色的方案数对 $10^9+7$ 取模后的余数。

输入格式

第一行包含一个整数 $t$ $(1 \le t \le 10\,000)$，表示测试数据的组数。接下来是 $t$ 组测试数据的描述。

每组测试数据的第一行包含三个整数 $n, k$ 和 $q$ $(3 \le n \le 10^6, 2 \le k \le 10^9, 0 \le q \le 300\,000)$，分别表示树的顶点数、可用颜色数以及执行的操作次数。

第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$ $(1 \le p_i < i)$，其中 $p_i$ 是顶点 $i$ 在树中的父节点。保证树的顶点按照深度优先遍历顺序编号，且在 $p_2, \dots, p_n$ 中，$1$ 至少出现两次。

接下来有 $q$ 行，第 $i$ 行包含一个整数 $v_i$ $(2 \le v_i \le n)$，表示第 $i$ 次操作的参数。

保证所有测试数据中 $n$ 的总和不超过 $10^6$，所有测试数据中 $q$ 的总和不超过 $300\,000$。

输出格式

对于每组测试数据，输出 $q+1$ 个数字，第一个数字是原始画作的潜力值，其余数字是每次操作执行后画作的潜力值。

样例

输入

2
3 4 5
1 1
2
3
2
3
3
9 4 8
1 2 2 1 5 5 1 8
9
8
3
5
4
3
9
8

输出

12
4
4
4
12
4
96
48
48
24
12
12
12
12
36

数据范围与提示

我们将树的高度定义为从根节点到其他顶点的简单路径上边的最大数量。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。