Codeforces 462D Appleman and Tree 树形dp

题目链接：点击打开链接

题意：

给定n个点的树，

0为根，下面n-1行表示每个点的父节点

最后一行n个数 表示每个点的颜色，0为白色，1为黑色。

把树分成若干个联通块使得每个联通块有且仅有一个黑点，问有多少种分法（结果mod1e9+7）

思路：

树形dp，每个点有2个状态，已经归属于某个黑点和未归属于某个黑点。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; #define N 300100 #define mod 1000000007 typedef long long ll; ll dp[N][2]; //dp[i][1]表示i点已经归属于某个黑点的方法数 //dp[i][0]表示i点未曾归属某个黑点的方法数 int n, col[N]; vector
     
      G[N]; void dfs(int u){ dp[u][1] = col[u]; dp[u][0] = col[u]^1; for(int i = 0; i < G[u].size(); i++){ int v = G[u][i]; dfs(v); ll old[2] = {dp[u][0], dp[u][1]}; dp[u][0] = (old[0]*dp[v][1] +old[0]*dp[v][0])%mod; dp[u][1] = (old[1]*dp[v][1] +old[1]*dp[v][0] +old[0]*dp[v][1])%mod; } } int main() { int i, j; while(~ scanf("%d",&n)){ for(i = 0; i < n; i++)G[i].clear(); for(i = 1; i < n; i++){ scanf("%d",&j); G[j].push_back(i); } for(i = 0; i < n; i++)scanf("%d",&col[i]); dfs(0); cout<