P17025 [ROI 2026 Day2] 好的染色 - 8

伊尔达尔决定投身抽象艺术。他选择了一棵有 $n$ 个顶点的**有根树**作为画作的基础：这是一张无环图，其中顶点 $1$ 被指定为**根**。根没有父节点；对于任意其他顶点 $u \ge 2$，从 $u$ 到根的路径上的第一个顶点称为 $u$ 的**父节点**，记作 $p_u$。以 $v$ 为父节点的顶点称为 $v$ 的**孩子**。没有孩子的顶点称为**叶子**。保证根至少有两个孩子。 我们对树执行深度优先遍历：首先访问根，然后按顺序递归地以同样方式访问其孩子的子树。树的顶点按照该深度优先遍历的顺序编号。因此，对于每个 $i$ 从 $1$ 到 $n$，顶点 $i$ 的子树中的顶点编号构成一段连续的整数。 设树中有 $m$ 片叶子。伊尔达尔将它们按编号升序写出，得到序列 $l_1 < l_2 < \ldots < l_m$，并添加边连接所有形如 $(l_j, l_{j+1})$ 的叶子对，同时连接 $l_m$ 和 $l_1$。所添加的环 $l_1 \to l_2 \to \ldots \to l_m \to l_1$ 称为**外环**。 伊尔达尔将得到的图画在平面上，方式如下：外环被画作一个圆，叶子 $l_1, l_2, \ldots, l_m$ 沿圆周逆时针排列，圆周上相邻顶点间的弧表示外环的边。树的其他顶点表示为位于圆内的不同点。树的边用顶点间的线段表示，且顶点和边的位置使得边线段之间没有公共内点。下图展示了树的一种绘制方式。 :::align{center}  ::: 在伊尔达尔的图中，外环圆周内部的平面部分被图的边分割成了 $m$ 个区域，称为**面**。如果两个不同的面共享一条边，则称它们为**相邻**的面。例如，上图中得到 5 个面，分别记为 $\Gamma_1, \Gamma_2, \Gamma_3, \Gamma_4$ 和 $\Gamma_5$。 :::align{center}  ::: 上图中相邻的面对为 $(\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)$。 为了完成画作，伊尔达尔计划将每个面染成 $k$ 种颜色之一。一种染色被称为**正确的**，如果相邻的面被染成不同的颜色。伊尔达尔将图画中不同正确染色的个数对 $10^9+7$ 取模的结果称为该图画的**潜能**。 在评估了初始图画的潜能之后，伊尔达尔对该图的边进行了 $q$ 次操作。考虑第 $i$ 次操作，它由一个数 $v_i$ 给出，并对连接顶点 $v_i$ 和 $p_{v_i}$ 的树边生效。如果该边当前在图中可见，则伊尔达尔从图中删除该边；如果该边当前不在图中，则重新画上。每次修改后，图中的面的集合可能发生变化：删除边时，两个面可能合并成一个；画上边时，一个面可能分裂成两个。例如，若在上图中删除边 $8 - 9$，则面 $\Gamma_4$ 和 $\Gamma_5$ 合并成一个面 $\Gamma_{4+5}$。 :::align{center}  ::: 此时图中相邻的面对为 $(\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$），分别表示树中的顶点数、可用颜色数和执行的操作次数。 每组数据的第二行包含 $p_2, p_3, \ldots, p_n$（$1 \le p_i < i$），其中 $p_i$ 是树中顶点 $i$ 的父节点。保证树的顶点按深度优先遍历顺序编号，且数值 $1$ 在 $p_2, \ldots, p_n$ 中出现至少两次。 随后是 $q$ 行，其中第 $i$ 行包含一个整数 $v_i$（$2 \le v_i \le n$），表示第 $i$ 次操作的参数。 保证所有测试数据中 $n$ 的总和不超过 $10^6$，所有测试数据中 $q$ 的总和不超过 $300\,000$。

输出 $q+1$ 个数：第一个数为初始图画的潜能，其余分别为每次操作后图画的潜能。

### 子任务 定义树的高度为从根到其他顶点的简单路径上的最大边数。 | 子任务 | 分数 | $n$ | $k$ | $q$ | 额外限制 | 依赖子任务 | |:---:|:---:|:---:|:---:|:---:|:---|:---:| | 1 | 6 | $n = 3$ | $k \le 4$ | $q \le 10 $ | $t \le 100$，$p_2 = p_3 = 1$ | | | 2 | 9 | $\sum n \le 1\,000$ | -- | $q = 0$ | $p_{i} = 2 \cdot \lfloor \frac{i}{2} \rfloor - 1$，$n$ 为奇数 | | | 3 | 10 | $\sum n \le 1\,000$ | -- | $\sum q \le 1\,000$ | $p_i = 1$ | 1 | | 4 | 4 | $n \le 9$ | $k \le 4$ | $q = 0 $ | $t \le 100$ | | | 5 | 3 | $n \le 9$ | $k \le 4$ | $q \le 10$ | $t \le 100$ | 4 | | 6 | 2 | $\sum n \le 1\,000$ | $k=2$ | $q = 0$ | -- | | | 7 | 11 | $\sum n \le 1\,000$ | -- | $q = 0$ | -- | 2, 4, 6 | | 8 | 15 | $\sum n \le 1\,000$ | -- | $\sum q \le 1\,000$ | -- | 1–7 | | 9 | 4 | $\sum n \le 5\,000$ | -- | $\sum q \le 5\,000$ | -- | 1–8 | | 10 | 3 | $\sum n \le 10\,000$ | -- | $\sum q \le 10\,000$ | -- | 1–9 | | 11 | 6 | $\sum n \le 100\,000$ | -- | $\sum q \le 5\,000$ | -- | 1–9 | | 12 | 7 | $\sum n \le 100\,000$ | -- | $\sum q \le 100\,000$ | 高度不超过 $20$ | 1, 4, 5 | | 13 | 14 | $\sum n \le 100\,000$ | -- | $\sum q \le 100\,000$ | -- | 1–12 | | 14 | 3 | $\sum n \le 300\,000$ | -- | $\sum q \le 300\,000$ | -- | 1–13 | | 15 | 3 | $\sum n \le 1\,000\,000$ | -- | $\sum q \le 300\,000$ | -- | 1–14 | 翻译由 DeepSeek V4 Pro 完成