B. Appleman and Tree 树形DP
题目大意：
给你一颗大小为 n 的树，1 号节点为根节点，每棵树染色，白色或者是黑色，求有多少种分割的方式，使得分割出来的连通块中有且仅有一个黑点
题解：
感觉自己真的很久没有刷题了，不太会写这个题目，想到了状态的定义，但是不知道怎么转移。
\(dp[u][0/1]\) 表示 \(u\) 这颗子树含有 \(0/1\) 个黑色节点的连通块的方案数。
-
如果子节点是白色，父节点是黑色，那么对 \(dp[u][1]\) 有贡献。
\(dp[u][1] *= dp[v][0]\)
-
如果子节点是白色，父节点也是白色，那么对 \(dp[u][0]\) 有贡献。
\(dp[u][0]*=dp[v][0]\)
-
如果子节点是黑色，父节点也是黑色，那么对 \(dp[u][1]\) 有贡献。断开
\(dp[u][1] *= dp[v][1]\)
-
如果子节点是黑色，父节点是白色，那么对 \(dp[u][1]\) 和 \(dp[u][0]\) 都有贡献，前者不断开，后者断开
\(dp[u][0]*=dp[v][1]\) \(dp[u][1]*=dp[v][1]\)
最后答案就是 \(dp[1][1]\)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 2e5+10;
const int mod = 1e9+7;
typedef long long ll;
int color[maxn],head[maxn],to[maxn<<1],nxt[maxn<<1],cnt,flag[maxn];
void add(int u,int v){
++cnt,to[cnt] = v,nxt[cnt] = head[u],head[u] = cnt;
}
ll dp[maxn][2];
void dfs1(int u){
if(color[u]) dp[u][1] = 1;
else dp[u][0] = 1;
for(int i=head[u];i;i=nxt[i]){
int v = to[i];
dfs1(v);
dp[u][1] = (dp[u][1]*(dp[v][0]+dp[v][1])%mod+dp[u][0]*dp[v][1])%mod;
dp[u][0] = dp[u][0]*(dp[v][0]+dp[v][1])%mod;
}
// printf("dp[%d][0]=%lld dp[%d][1]=%lld\n",u,dp[u][0],u,dp[u][1]);
}
int main(){
int n;
scanf("%d",&n);
for(int i=1,x;i<n;i++){
scanf("%d",&x);
add(x,i);
}
for(int i=0,x;i<n;i++){
scanf("%d",&x);
color[i] = x;
}
dfs1(0);
printf("%lld\n",dp[0][1]);
return 0;
}