P11039 【MX-X3-T6】「RiOI-4」TECHNOPOLIS 2085

原题链接：。 ---  （图片来自 phigros 曲绘，侵删。） 啊～啊～啊咦～啊咦～哦→啊↑啊↓啊～嗯～哎哎↑哎哦哎嗯～哦啊~爱↖爱↑爱↗爱↑爱↑啊～啊～啊咦～啊咦～啊→啊↑啊↓啊～嗯嗯↓嗯↓滴嘚滴嘚唔↑～～嘟←嘟↖️嘟↑嘟↗️嘟→嘟↘️嘟↓ 你说得对，但是这里是梦熊周赛题，不是出题人用来发电的地方，所以你需要做一道图论题。

约定 $\operatorname{lca}_G(u,v)$ 表示编号为 $u,v$ 的结点在有标号有根树 $G$ 上的最近共同祖先。给定一棵根编号为 $1$，大小为 $n$ ，结点编号为 $1\sim n$ 的有根树 $T$ 与一个大小为 $m$ 的点集 $S$。你需要求出有多少个**不同的**大小为 $n$ 的结点编号为 $1\sim n$ 的有根树 $T'$，满足对于任意 $u,v\in S$，有 $\operatorname{lca}_T(u,v)=\operatorname{lca}_{T'}(u,v)$。 答案对 $998\,244\,353$ 取模。 我们称两颗大小为 $n$ 的有标号有根树是**不同的**，当且仅当以下二者至少一个成立： - 它们的根节点不同。 - 存在一条边，在一棵树中未出现，而在另一棵树中出现。

无

无

**【样例解释 #1】** 只有与 $T$ 完全相同的树满足要求。 **【样例解释 #2】** 对于样例 2，满足要求的树的所有 $8$ 种 $p$ 数组如下（根的 $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\}$。 **【数据范围】** **本题开启捆绑测试。** |子任务|分数|$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$| 对于 $100\%$ 的数据，$2\le m\le n\le 10^6$，保证输入的 $p$ 对应了一棵有标号有根树，$S$ 描述了一个结点组成的集合。