#E. 「RiOI-4」TECHNOPOLIS 2085

    传统题 1000ms 512MiB

「RiOI-4」TECHNOPOLIS 2085

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

(图片来自 phigros 曲绘,侵删。)

啊~啊~啊咦~啊咦~哦→啊↑啊↓啊~嗯~哎哎↑哎哦哎嗯~哦啊~爱↖爱↑爱↗爱↑爱↑啊~啊~啊咦~啊咦~啊→啊↑啊↓啊~嗯嗯↓嗯↓滴嘚滴嘚唔↑~~嘟←嘟↖️嘟↑嘟↗️嘟→嘟↘️嘟↓

你说得对,但是这里是梦熊周赛题,不是出题人用来发电的地方,所以你需要做一道图论题。

题目描述

约定 lcaG(u,v)\operatorname{lca}_G(u,v) 表示编号为 u,vu,v 的结点在有标号有根树 GG 上的最近共同祖先。给定一棵根编号为 11,大小为 nn ,结点编号为 1n1\sim n 的有根树 TT 与一个大小为 mm 的点集 SS。你需要求出有多少个不同的大小为 nn 的结点编号为 1n1\sim n 的有根树 TT',满足对于任意 u,vSu,v\in S,有 $\operatorname{lca}_T(u,v)=\operatorname{lca}_{T'}(u,v)$。

答案对 998244353998\,244\,353 取模。

我们称两颗大小为 nn 的有标号有根树是不同的,当且仅当以下二者至少一个成立:

  • 它们的根节点不同。
  • 存在一条边,在一棵树中未出现,而在另一棵树中出现。

输入格式

第一行两个正整数 n,mn,m

第二行 n1n-1 个正整数 p2,p3,,pnp_2,p_3,\cdots,p_n 表示编号为 2n2\sim n 的结点的父亲编号。

最后一行 mm 个正整数,表示选出的集合 SS 中结点的编号。

输出格式

一行一个整数,表示答案对 998244353998\,244\,353 取模的值。

样例

5 3
1 1 2 2
3 4 5
1

样例 1 解释

只有与 TT 完全相同的树满足要求。

5 3
1 1 2 2
2 3 4
8

样例 2 解释

对于样例 2,满足要求的树的所有 88pp 数组如下(根的 pip_i00):

$\{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\}$。

20 10
20 8 7 16 3 15 1 10 17 3 13 15 1 17 1 14 14 8 4
3 7 10 19 15 13 4 6 18 5
553508927

数据范围

本题开启捆绑测试。

子任务 分数 nn\le mm\le
11 77 1010
22 1818 200200
33 2222 10510^5
44 1717 10610^6 1010
55 3636 10610^6

对于 100%100\% 的数据,2mn1062\le m\le n\le 10^6,保证输入的 pp 对应了一棵有标号有根树,SS 描述了一个结点组成的集合。

【MX-X3】梦熊 X 组 · 面包赛 & RiOI Round 4

未参加
状态
已结束
规则
IOI
题目
6
开始于
2024-9-8 13:30
结束于
2024-9-8 18:00
持续时间
4.5 小时
主持人
参赛人数
146