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];
vectorG[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<
