#P6904. 拿钱了
拿钱了
题目描述
给定一棵树 ,其中每个顶点的度数均不为 。树上的顶点按 DFS 序编号为 。将所有叶子按编号从小到大排列为 ,在 上加入边 ,得到图 。
从 中选择一个边集,保留 的全部顶点。要求所得子图的每个连通分量都是一棵树,且恰有 或 个顶点。求符合条件的边集数,对 取模。
输入格式
第一行一个整数 ,表示顶点数。
第二行 个非负整数,依次表示顶点 至顶点 的父亲。保证顶点按 DFS 序编号。
输出格式
输出一个整数,表示符合条件的边集数对 取模后的值。
样例
4
1 1 1
13
加入叶子间的边后,得到的图是完全图。
6
1 1 3 3 1
34
11
1 1 3 4 4 3 3 1 9 9
737
数据范围
| 原题子任务 | 上限 | 分值 |
|---|---|---|
| 1 | 20 | |
| 2 | 30 | |
| 3 | 50 |
原题每个子任务须通过组内全部测试点才得分。