Codeforces Round #275 (Div. 1)D（树形DP）_html/css_WEB-ITnose

D. ランダム関数とツリー

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

n 個の頂点から構成されるルート付きツリー。 1 から n までの整数で番号を付けましょう。ツリーのルートは頂点 1 です。各 i?>?1 頂点 i の直接の親は pi です。頂点 i はその直接の親 pi の子であると言います。

最初にすべての頂点を赤色でペイントしました。あなたは木のいくつかの頂点を再ペイントしたいと考えています。ペイントを実行するには、ツリーのルートを引数として呼び出す関数paintを使用します。この関数の疑似コードは次のとおりです:

count = 0 // global integer variable rnd() { // this function is used in paint code    return 0 or 1 equiprobably}paint(s) {    if (count is even) then paint s with white color    else paint s with black color    count = count + 1        if rnd() = 1 then children = [array of vertex s children in ascending order of their numbers]    else children = [array of vertex s children in descending order of their numbers]    for child in children { // iterating over children array        if rnd() = 1 then paint(child) // calling paint recursively    }}

この関数の結果として、一部の頂点の色が白または黒に変わり、一部の頂点は赤のままになる可能性があります。

あなたのタスクは、可能な個別の色の数を決定することです。木の頂点。 Paint(1) の 1 回の呼び出しでこのカラーリングを取得できる確率がゼロ以外の場合、カラーリングは可能であると仮定します。これらの色付けにおいて異なる色で塗られた頂点のペアが存在する場合、色付けは異なるものとみなします。必要な数値が非常に大きい可能性があるため、1000000007 (109?+?7) による除算の余りを求めます。

入力

最初の行には、単一の整数 n (2?≤?n?≤?105) が含まれています。 ?ツリー内の頂点の数です。

2 行目には、n?-?1 整数 p2,?p3,?...,?pn (1?≤?pi?

出力

単一の整数を出力しますか?問題の答え modulo 1000000007 (109?+?7)

サンプルテスト

入力

41 2 1

出力

入力

すごい

出力

注

最初のサンプルの可能なすべての着色パターンを以下に示します。

题意：RT

思路：最初にこの関数の数を不要被吓到、实际上就是求何种子树

dp[u][0] 表示がuである根、子树大小が奇数の方法案

dp[u][1] 表示がuである根、子树大小が奇数の方法案数

この样は按升序算の結果、将这个乘2は升序+降順の結果を得ることができますが、中期には部分算重があります

考虑这样两种情况

1．如果u的每孩子大小都是奇数，那么選択的任意数孩子のこの情况都は重複了

2.如果u的每孩子大小都是奇数，那么选任意奇数の孩子的この情况も重复了（自己画一下图就知道了）

细节看代码~