P11039 [MX-X3-T6] "RiOI-4" TECHNOPOLIS 2085

Original link: 。 ---  (The image is from a Phigros song illustration. Please contact for removal if needed.) Ah~ ah~ ah yi~ ah yi~ oh→ ah↑ ah↓ ah~ um~ ai ai↑ ai oh ai um~ oh ah~ love↖ love↑ love↗ love↑ love↑ ah~ ah~ ah yi~ ah yi~ ah→ ah↑ ah↓ ah~ um um↓ um↓ di de di de wu↑ ~~ du← du↖️ du↑ du↗️ du→ du↘️ du↓ You are right, but this is a Dream Bear weekly contest problem, not a place for the setter to "generate electricity", so you need to solve a graph theory problem.

By convention, $\operatorname{lca}_G(u,v)$ denotes the lowest common ancestor of nodes with labels $u,v$ in a labeled rooted tree $G$. You are given a rooted tree $T$ with root label $1$, size $n$, and node labels $1\sim n$, as well as a node set $S$ of size $m$. You need to find how many **distinct** labeled rooted trees $T'$ of size $n$ with node labels $1\sim n$ satisfy that for any $u,v\in S$, we have $\operatorname{lca}_T(u,v)=\operatorname{lca}_{T'}(u,v)$. Output the answer modulo $998\,244\,353$. We say two labeled rooted trees of size $n$ are **different** if and only if at least one of the following holds: - Their root nodes are different. - There exists an edge that appears in one tree but not in the other.

The first line contains two positive integers $n,m$. The second line contains $n-1$ positive integers $p_2,p_3,\cdots,p_n$, where $p_i$ is the parent label of node $i$ for $i=2\sim n$. The last line contains $m$ positive integers, indicating the labels of the selected nodes in the set $S$.

One line with one integer, the answer modulo $998\,244\,353$.

**Sample Explanation #1** Only the tree that is exactly the same as $T$ satisfies the requirement. **Sample Explanation #2** For sample 2, all $8$ valid $p$ arrays are as follows (the root has $p_i=0$): $\{0,1,1,2,1\},\{0,1,1,2,2\},\{0,1,1,2,3\},\{0,1,1,2,4\},$ $\{0,1,1,5,2\},\{0,5,1,2,1\},\{0,1,5,2,1\},\{5,1,1,2,0\}$。 **Constraints** **This problem uses bundled testdata.** |Subtask|Score|$n\le$|$m\le$| |:-:|:-:|:-:|:-:| |$1$|$7$|$10$|$10$| |$2$|$18$|$200$|$200$| |$3$|$22$|$10^5$|$10^5$| |$4$|$17$|$10^6$|$10$| |$5$|$36$|$10^6$|$10^6$| For $100\%$ of the data, $2\le m\le n\le 10^6$. It is guaranteed that the input $p$ describes a labeled rooted tree, and $S$ describes a set of nodes. Translated by ChatGPT 5