[CF 482D] Random Function and Tree

作法：

令$dp[x][b]$代表以$x$為根的子樹中塗了個數的奇偶性為$b$的節點有幾種塗法，首先算出「選出這棵子樹要塗色的集合」有幾種方法，再來算考慮黑白色時有幾種方法。不難用一次DP算出這棵子樹塗上奇數（或偶數）個點時有幾種塗法（不考慮黑白的問題），但對於某一種塗法來說，從左邊塗過來根從右邊塗過來可能不一樣，也可能一樣。而所求就會是剛才求出的值的兩倍，再扣掉「從左塗和從右塗會一樣」的不考慮黑白的塗法數，因此接下來要想辦法算出後者的值。假設$x$的子樹為$T_1,...,T_r$，並且這種塗法分別在每個子樹裡塗了$a_1,...,a_r$個點。那麼從左邊塗過來的話，$T_i$的根節點的顏色就和$a_1+...+a_{i-1}$的奇偶性有關（注意到當根節點顏色確定，整棵子樹的顏色就確定了），從右邊塗過來則是和$a_{i+1}+...+a_r$的奇偶性有關。因此當兩種塗法一樣時，代表對於所有$a_i>0$，$a_1+...+a_{i-1}$和$a_{i+1}+...+a_r$的奇偶性相同，又等價於對於所有$a_i>0$，$a_1+...+a_{i-1}+a_{i+1}+...+a_r$為偶數，也就是所有$a_i>0$的$i$都必須和$a_1+...+a_r$的雞偶性相同。不難得到滿足這種條件的$a_i$只有兩種可能，一種是全部都是偶數，另一種是$a_1,...,a_r$中每個數不是奇數就是$0$，並且裡面有奇數個奇數。這兩個也都不難用DP對子節點掃一次得出，因此就完成轉移了。

code :

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
const int maxn=200000+10 ;
 
LL dp[maxn][2] ;
vector<int> v[maxn] ;
void dfs(int x)
{
    if(v[x].empty())
    {
        dp[x][0]=0 ;
        dp[x][1]=1 ;
        return ;
    }
    dp[x][0]=1 ; dp[x][1]=0 ;
    for(auto i : v[x])
    {
        dfs(i) ;
        LL t0=dp[x][0] , t1=dp[x][1] ;
        dp[x][0]=(t0*(dp[i][0]+1)+t1*dp[i][1])%MOD ;
        dp[x][1]=(t0*dp[i][1]+t1*(dp[i][0]+1))%MOD ;
    }
    dp[x][0]*=2 ; dp[x][0]%=MOD ;
    dp[x][1]*=2 ; dp[x][1]%=MOD ;
 
    LL sub0=1 , sub1[2]={1,0} ;
    for(auto i : v[x])
    {
        sub0=sub0*(dp[i][0]+1)%MOD ;
        LL t0=sub1[0] , t1=sub1[1] ;
        sub1[0]=(t0+t1*dp[i][1])%MOD ;
        sub1[1]=(t1+t0*dp[i][1])%MOD ;
    }
    dp[x][0]-=sub0 ; if(dp[x][0]<0) dp[x][0]+=MOD ;
    dp[x][1]-=sub1[1] ; if(dp[x][1]<0) dp[x][1]+=MOD ;
    swap(dp[x][0],dp[x][1]) ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=2;i<=n;i++)
    {
        int x ; scanf("%d",&x) ;
        v[x].push_back(i) ;
    }
    dfs(1) ;
    printf("%d\n",(dp[1][0]+dp[1][1])%MOD) ;
}