UOJ Logo

NOI.AC

3S 512MB

#146. tree

统计

树(tree)

【题目描述】

HZY给一棵有根树,开始每个点是黑色的,每轮操作会随机选一个黑点,然后把这个点到根路径上的所有点染白,问要把所有点全部染白期望需要几轮?

【输入格式】

第一行一个正整数 n。

接下来一行 n − 1 个正整数,第 i 个数 pi 表示第 i + 1 号节点的父亲。

【输出格式】

输出一行,表示期望轮数,为了方便,这里只用输出模 998244353 意义下的值。

【样例输入 1】

3
1 1

【样例输出 1】

332748120

【样例输入 2】

3
1 2

【样例输出 2】

831870296

【样例说明】

可以证明最后的期望形式可以表达成x/y的形式,其中 x, y 均为正整数。x/y在模质数 p 意义下与 $x * y_{−1}$ 相等,其中 $y_{−1}$ 为 y 在模 p 意义下的逆元。

对于样例 1,可以证明期望为 7/3,所以答案为 $7 ∗ 3_{−1} mod p = 332748120 $。

【数据范围】

对于 30 % 的数据,n ≤ 20。

对于 70 % 的数据,n ≤ 106。

对于 100 % 的数据,$n ≤ 107,p_i ≤ i$。