No.828 全方位神童数
タグ : / 解いたユーザー数 22
作問者 :
問題文
青木くんは 頂点
青木くんは木
青木くんは根付き木に対して、「頂点
また
(各頂点が神童かどうかは、どの頂点を根とするかに依存することに注意して下さい)
例えば下図のような根付き木を考えると、黄色の頂点が神童であり、神童数は4となります。
ここで
また
青木くんは
頂点
たくさんの数を伝えるのは大変なので、数列
但しこの値は非常に大きくなりうるので、
入力
1行目に木の頂点数
2行目には答えの計算に用いる数列
3行目から
※入力が多めなので注意して下さい。
制約
- 入力されるグラフは
頂点の木である。 - 入力は全て整数である。
出力
最後に改行して下さい。
サンプル
サンプル1
入力
3 0 0 0 1 2 2 3
出力
6
頂点1,2,3を根とみなした様子が以下の図です。黄色に塗られた頂点が神童です。
サンプル2
入力
3 0 0 0 1 3 3 2
出力
4
頂点1,2,3を根とみなした様子が以下の図です。黄色に塗られた頂点が神童です。
サンプル3
入力
20 397391841 679700971 145606697 977415091 513786611 99670444 666370425 151199845 823785563 113697511 311512752 592551093 141690528 337950684 441783513 543190271 462296398 851050627 141769971 473127767 17 19 18 11 19 6 20 8 8 16 20 3 13 9 11 10 15 8 11 20 17 18 14 8 1 20 2 5 11 7 11 4 5 20 1 12 2 13
出力
598344873
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。