C1092 [Contest #6]另一道树题

内存限制:256 MB 时间限制:1000 ms

题目描述

短发pinga野郞有一棵 $N$ 个节点的有根树,其中 $1$ 号节点为根。

现在她想在这棵树上进行一种奇妙的游戏。游戏开始时,她会在其中一些节点(至少两个)上摆放一个棋子。在游戏的每个回合中,她会将所有棋子移动到父亲节点上(如棋子位于根节点则不移动)。移动完所有棋子后,如果有两个棋子位于同一个节点,游戏结束,否则进行下一回合直到游戏结束。

定义游戏的有趣程度为游戏结束前进行的总回合数。现在,pinga野郞想知道,对于所有可能的 $2^N-N-1$ 种初始摆放方案,游戏的有趣程度之和是多少。请你将答案对 $998244353$ 取模后输出。

输入格式

第一行包含一个整数 $N$,保证 $2\leq N\leq 2*10^5$。

第二行包含 $N-1$ 个整数 $p_2,p_3,\cdots,p_N$,其中 $p_i$ 表示 $i$ 号节点的父亲,保证 $1\leq p_i<i$。

输出

输出一个整数,表示答案。

样例

样例输入 1

3 1 2

样例输出 1

6

提示

样例解释:

初始摆放有棋子的节点集合共有 $\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$ 四种可能,其中 $\{1,2\},\{1,2,3\}$ 的有趣程度为 $1$,$\{2,3\},\{1,3\}$ 的有趣程度为 $2$。