TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P6851
  • 問題
  • P6851弹珠
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 1s,512m
    問題説明

    给定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