中文
日本語
English
| P6851弹珠 | ||
|
問題説明
给定n+1个点的树，节点编号0到n。0号点为根。每个点可以选择放或不放弹珠。一开始你有一个空盒子。 每一轮依次进行以下操作：
1.将根节点0的弹珠加入盒子。
2.每个点的弹珠移向父亲。
3.如果一个点有至少2个弹珠，则将该点的弹珠全部扔掉。
如果树中仍有弹珠，继续下一轮。
共有$2^{n+1}$种放弹珠的方案，计算所有方案放到盒子里的弹珠数量总和，取模$1e9+7$。 $1<=n<2*10^5$入力形式
第一行，一个整数n
第二行，n个空格间隔的整数，第i个数表示i号节点的父亲节点。
出力形式
一个整数
サンプル入力 1
2
0 0
サンプル出力 1
8
サンプル入力 2
5
0 1 1 0 4
サンプル出力 2
96
サンプル入力 3
31
0 1 0 2 4 0 4 1 6 4 3 9 7 3 7 2 15 6 12 10 12 16 5 3 20 1 25 20 23 24 23
サンプル出力 3
730395550
サンプル入力 4
70
0 1 2 1 3 5 6 0 3 1 1 9 1 13 8 4 5 17 0 15 10 4 1 13 21 10 0 8 7 24 8 6 22 1 1 26 10 5 38 6 1 40 27 16 31 20 31 28 41 39 44 44 22 47 46 45 41 11 10 37 18 53 15 47 37 21 29 46 12 66
サンプル出力 4
868829654
ソース arc086e