#P6904. 拿钱了

    ID: 6735 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-树形 DP计数 DPDFS 序滚动数组

拿钱了

题目描述

给定一棵树 TT,其中每个顶点的度数均不为 22。树上的顶点按 DFS 序编号为 1,2,…,n1,2,\ldots,n。将所有叶子按编号从小到大排列为 a1,a2,…,aka_1,a_2,\ldots,a_k,在 TT 上加入边 (a1,a2),…,(ak−1,ak),(ak,a1)(a_1,a_2),\ldots,(a_{k-1},a_k),(a_k,a_1),得到图 GG。

从 GG 中选择一个边集,保留 GG 的全部顶点。要求所得子图的每个连通分量都是一棵树,且恰有 11 或 33 个顶点。求符合条件的边集数,对 998244353998244353 取模。

输入格式

第一行一个整数 nn,表示顶点数。

第二行 n−1n-1 个非负整数,依次表示顶点 22 至顶点 nn 的父亲。保证顶点按 DFS 序编号。

输出格式

输出一个整数,表示符合条件的边集数对 998244353998244353 取模后的值。

样例

4
1 1 1
13

加入叶子间的边后,得到的图是完全图。

6
1 1 3 3 1
34
11
1 1 3 4 4 3 3 1 9 9
737

数据范围

原题子任务 nn 上限 分值
1 100100 20
2 10001000 30
3 100000100000 50

原题每个子任务须通过组内全部测试点才得分。

原 PDF 题面