P17025 [ROI 2026 Day2] Good Coloring - 8

Ildar decided to devote himself to abstract art. He chose a **rooted tree** with $n$ vertices as the basis of his painting: it is an acyclic graph in which vertex $1$ is designated as the **root**. The root has no parent; for any other vertex $u \ge 2$, the first vertex on the path from $u$ to the root is called the **parent** of $u$, denoted by $p_u$. Vertices whose parent is $v$ are called the **children** of $v$. A vertex with no children is called a **leaf**. It is guaranteed that the root has at least two children. We perform a depth-first traversal of the tree: first visit the root, then recursively visit the subtrees of its children in order in the same way. The vertices of the tree are numbered in the order of this depth-first traversal. Therefore, for each $i$ from $1$ to $n$, the vertex numbers in the subtree of vertex $i$ form a contiguous interval of integers. Let the tree have $m$ leaves. Ildar writes them out in increasing order of their indices to get the sequence $l_1 < l_2 < \ldots < l_m$, and adds edges connecting every pair of leaves of the form $(l_j, l_{j+1})$, and also connects $l_m$ and $l_1$. The added cycle $l_1 \to l_2 \to \ldots \to l_m \to l_1$ is called the **outer cycle**. Ildar draws the resulting graph on the plane as follows: the outer cycle is drawn as a circle, and the leaves $l_1, l_2, \ldots, l_m$ are placed counterclockwise along the circumference. The arcs between adjacent vertices on the circumference represent the edges of the outer cycle. The other vertices of the tree are represented as distinct points inside the circle. The tree edges are drawn as line segments between their endpoints, and the positions of vertices and edges are such that the edge segments have no common interior points. The figure below shows one possible drawing of the tree. :::align{center}  ::: In Ildar's drawing, the part of the plane inside the outer cycle is divided by the edges of the graph into $m$ regions, called **faces**. If two different faces share an edge, they are called **adjacent** faces. For example, the drawing above produces 5 faces, denoted by $\Gamma_1, \Gamma_2, \Gamma_3, \Gamma_4$ and $\Gamma_5$. :::align{center}  ::: In the figure above, the adjacent face pairs are $(\Gamma_1, \Gamma_2)$, $(\Gamma_1, \Gamma_5)$, $(\Gamma_2, \Gamma_3)$, $(\Gamma_2, \Gamma_4)$, $(\Gamma_2, \Gamma_5)$, $(\Gamma_3, \Gamma_4)$, and $(\Gamma_4, \Gamma_5)$. To finish the painting, Ildar plans to color each face with one of $k$ colors. A coloring is called **proper** if adjacent faces are colored with different colors. Ildar calls the number of different proper colorings of the drawing modulo $10^9+7$ the **potential** of the drawing. After evaluating the potential of the initial drawing, Ildar performs $q$ operations on the edges of the graph. Consider the $i$-th operation: it is given by a number $v_i$ and acts on the tree edge connecting vertex $v_i$ and $p_{v_i}$. If this edge is currently visible in the drawing, Ildar deletes it from the drawing; if this edge is currently not in the drawing, he draws it again. After each modification, the set of faces in the drawing may change: when an edge is deleted, two faces may merge into one; when an edge is drawn, one face may split into two. For example, if we delete the edge $8 - 9$ in the figure above, then faces $\Gamma_4$ and $\Gamma_5$ merge into a single face $\Gamma_{4+5}$. :::align{center}  ::: Now the adjacent face pairs are $(\Gamma_1, \Gamma_2)$, $(\Gamma_1, \Gamma_{4+5})$, $(\Gamma_2, \Gamma_3)$, $(\Gamma_2, \Gamma_{4+5})$, and $(\Gamma_3, \Gamma_{4+5})$. After each operation, you need to determine the potential of the drawing again, i.e., the number of proper colorings of the faces using at most $k$ colors modulo $10^9+7$.

The first line contains an integer $t$ ($1 \le t \le 10\,000$), the number of testdata sets. The description of the $t$ testdata sets follows. The first line of each testdata set contains three integers $n$, $k$, and $q$ ($3 \le n \le 10^6$, $2 \le k \le 10^9$, $0 \le q \le 300\,000$), denoting the number of vertices in the tree, the number of available colors, and the number of operations performed. The second line of each testdata set contains $p_2, p_3, \ldots, p_n$ ($1 \le p_i < i$), where $p_i$ is the parent of vertex $i$ in the tree. It is guaranteed that the vertices are numbered in depth-first traversal order, and that the value $1$ appears at least twice in $p_2, \ldots, p_n$. Then follow $q$ lines, where the $i$-th line contains an integer $v_i$ ($2 \le v_i \le n$), denoting the parameter of the $i$-th operation. It is guaranteed that across all testdata sets, the sum of $n$ does not exceed $10^6$, and the sum of $q$ does not exceed $300\,000$.

Output $q+1$ numbers. The first number is the potential of the initial drawing, and the remaining numbers are the potential of the drawing after each operation.

### Subtasks Define the height of the tree as the maximum number of edges on a simple path from the root to any other vertex. | Subtask | Score | $n$ | $k$ | $q$ | Additional constraints | Depends on subtasks | |:---:|:---:|:---:|:---:|:---:|:---|:---:| | 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$ is odd | | | 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$ | Height does not exceed $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 | Translated by DeepSeek V4 Pro. Translated by ChatGPT 5