#P18908. [2026多校联测]叶环独立集
[2026多校联测]叶环独立集
叶环独立集
题目描述
给定一棵有 个顶点的有根树,顶点编号为 ,根为 。对于每个 ,给定其父亲 ,且 。没有孩子的顶点称为叶子。
从根出发进行深度优先遍历,每个顶点的孩子按编号从小到大访问。设叶子的访问顺序为 。
构造一个无向简单图 ,包含以下边:
- 原树的所有父子边;
- 对于 ,加入边 ;
- 加入边 。
若新增的边与已有边重复,只保留一条;不加入自环。因此,只有一个叶子时不增加边,只有两个叶子时只增加它们之间的一条边。
一个顶点集合是独立集,当且仅当集合中任意两个不同顶点之间都没有边。请计算 的独立集数量(包括空集),答案对 取模。
输入格式
第一行包含一个整数 。
第二行包含 个整数 。
输出格式
输出一个整数,表示独立集数量对 取模的结果。
样例 1
输入
7
1 1 2 2 3 3
输出
21
样例解释
叶子的访问顺序为 ,增加的边构成一个四边形。最终图共有 个独立集。
数据范围与子任务
对于所有数据,,。允许一个顶点只有一个孩子。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 15 | |
| 2 | 25 | ,叶子数不超过 |
| 3 | 15 | 原树为以 为中心的星形树 |
| 4 | 45 | 无 |
各子任务独立计分,需通过该子任务的全部测试点才能获得相应分数。
更多样例见附加文件 samples.zip。