#P18908. [2026多校联测]叶环独立集

[2026多校联测]叶环独立集

叶环独立集

题目描述

给定一棵有 nn 个顶点的有根树,顶点编号为 1,2,…,n1,2,\ldots,n,根为 11。对于每个 i>1i>1,给定其父亲 pip_i,且 pi<ip_i<i。没有孩子的顶点称为叶子。

从根出发进行深度优先遍历,每个顶点的孩子按编号从小到大访问。设叶子的访问顺序为 l1,l2,…,lkl_1,l_2,\ldots,l_k。

构造一个无向简单图 GG,包含以下边:

  • 原树的所有父子边;
  • 对于 1≤i<k1\le i<k,加入边 (li,li+1)(l_i,l_{i+1});
  • 加入边 (lk,l1)(l_k,l_1)。

若新增的边与已有边重复,只保留一条;不加入自环。因此,只有一个叶子时不增加边,只有两个叶子时只增加它们之间的一条边。

一个顶点集合是独立集,当且仅当集合中任意两个不同顶点之间都没有边。请计算 GG 的独立集数量(包括空集),答案对 10000000071000000007 取模。

输入格式

第一行包含一个整数 nn。

第二行包含 n−1n-1 个整数 p2,p3,…,pnp_2,p_3,\ldots,p_n。

输出格式

输出一个整数,表示独立集数量对 10000000071000000007 取模的结果。

样例 1

输入

7
1 1 2 2 3 3

输出

21

样例解释

叶子的访问顺序为 4,5,6,74,5,6,7,增加的边构成一个四边形。最终图共有 2121 个独立集。

数据范围与子任务

对于所有数据,4≤n≤1064\le n\le 10^6,1≤pi<i1\le p_i<i。允许一个顶点只有一个孩子。

子任务 分值 附加限制
1 15 n≤20n\le20
2 25 n≤105n\le10^5,叶子数不超过 88
3 15 原树为以 11 为中心的星形树
4 45 无

各子任务独立计分,需通过该子任务的全部测试点才能获得相应分数。

更多样例见附加文件 samples.zip。