题意：
给出一棵树，每个节点都被标记了黑或白色，要求把这棵树的其中k条变切换，划分成k+1棵子树，每颗子树必须有1个黑色节点，求有多少种划分方法。
题解：
树形dp
dp[x][0]表示是以x为根的树形成一块不含黑色点的方案数
dp[x][1]表示是以x为根的树形成一块含一个黑色点方案数
//зїеп:1085422276
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
#include <stack>
typedef long long ll;
#define inf 100000000
#define mod 1000000007
using namespace std; inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//*************************************** struct ss
{ int to,next;
}e[*];
ll dp[][];
int head[],t,vis[],cl[];
void init(){
memset(head,,sizeof(head));
t=;
}
void add(int u,int v)
{
e[t].next=head[u];
e[t].to=v;
head[u]=t++;
}
void dfs(int x,int pre)
{
//vis[x]=1;
dp[x][cl[x]]=;
for(int i=head[x];i;i=e[i].next)
{
if(e[i].to==pre)continue;
dfs(e[i].to,x);
if(cl[x]==){
dp[x][]=(dp[x][]*dp[e[i].to][]%mod+dp[x][]*dp[e[i].to][])%mod;
}
else { dp[x][]=(dp[x][]*dp[e[i].to][]%mod+dp[x][]*dp[e[i].to][]%mod+dp[x][]*dp[e[i].to][])%mod;
dp[x][]=(dp[x][]*dp[e[i].to][]%mod+dp[x][]*dp[e[i].to][])%mod;
} }
} int main()
{
init();
int n;
scanf("%d",&n);
int x;
for(int i=;i<n-;i++){
scanf("%d",&x);
add(i+,x);
add(x,i+);
}
for(int i=;i<n;i++)
scanf("%d",&cl[i]);
dfs(,-);
cout<<dp[][]<<endl;
return ;
}
代码