「RiOI-4」TECHNOPOLIS 2085
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
(图片来自 phigros 曲绘,侵删。)
啊~啊~啊咦~啊咦~哦→啊↑啊↓啊~嗯~哎哎↑哎哦哎嗯~哦啊~爱↖爱↑爱↗爱↑爱↑啊~啊~啊咦~啊咦~啊→啊↑啊↓啊~嗯嗯↓嗯↓滴嘚滴嘚唔↑~~嘟←嘟↖️嘟↑嘟↗️嘟→嘟↘️嘟↓
你说得对,但是这里是梦熊周赛题,不是出题人用来发电的地方,所以你需要做一道图论题。
题目描述
约定 表示编号为 的结点在有标号有根树 上的最近共同祖先。给定一棵根编号为 ,大小为 ,结点编号为 的有根树 与一个大小为 的点集 。你需要求出有多少个不同的大小为 的结点编号为 的有根树 ,满足对于任意 ,有 $\operatorname{lca}_T(u,v)=\operatorname{lca}_{T'}(u,v)$。
答案对 取模。
我们称两颗大小为 的有标号有根树是不同的,当且仅当以下二者至少一个成立:
- 它们的根节点不同。
- 存在一条边,在一棵树中未出现,而在另一棵树中出现。
输入格式
第一行两个正整数 。
第二行 个正整数 表示编号为 的结点的父亲编号。
最后一行 个正整数,表示选出的集合 中结点的编号。
输出格式
一行一个整数,表示答案对 取模的值。
样例
5 3
1 1 2 2
3 4 5
1
样例 1 解释
只有与 完全相同的树满足要求。
5 3
1 1 2 2
2 3 4
8
样例 2 解释
对于样例 2,满足要求的树的所有 种 数组如下(根的 为 ):
$\{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
数据范围
本题开启捆绑测试。
子任务 | 分数 | ||
---|---|---|---|
对于 的数据,,保证输入的 对应了一棵有标号有根树, 描述了一个结点组成的集合。
【MX-X3】梦熊 X 组 · 面包赛 & RiOI Round 4
- 状态
- 已结束
- 规则
- IOI
- 题目
- 6
- 开始于
- 2024-9-8 13:30
- 结束于
- 2024-9-8 18:00
- 持续时间
- 4.5 小时
- 主持人
- 参赛人数
- 146