题意:
给定一棵树,将树分成k个连通块,并且每个连通块内只有一个节点的方案数。
思路:
这个实在是想不出来啊,标解是开个dp[u][2]数组,表示只考虑u这颗子树并且u这个节点是否在有黑棋子的连通块中的方案数。
初始化就是如果黑色dp[u][1]=1,否则dp[u][0]=1;
转移也很骚:
枚举每个子树,由于乘法原理我们发现子树之间是相互独立的,
dp[u][1]=dp[u][1](dp[j][0]+dp[j][1])+dp[u][0](dp[j][1])
dp[u][0]=dp[u][0]*(dp[j][0]+dp[j][1])
为何这么转移?如果这个点已经被包括在有黑点的连通块中了,那么它儿子的子树有没有被包括都可以,由于是同一棵树那就用加法原理,但如果他之前没被包括,他可以通过与被包括黑棋子的子树相连。同理dp[u][0]的转移不再赘述。
AC代码:
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int h[N];
int e[N*2];
int ne[N*2];
int idx;
const int mod=1e9+7;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n;
int c[N];
long long dp[N][2];
void dfs(int u,int fa)
{
if(c[u])
dp[u][1]=1;
else
dp[u][0]=1;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa)
continue;
dfs(j,u);
dp[u][1]=(1ll*dp[u][1]*(dp[j][0]+dp[j][1])%mod+1ll*dp[u][0]*dp[j][1]%mod)%mod;
dp[u][0]=dp[u][0]*(dp[j][0]+dp[j][1])%mod;
}
}
int main()
{
memset(h,-1,sizeof h);
cin>>n;
for(int i=1;i<n;i++)
{
int x;
cin>>x;
add(i,x);
add(x,i);
}
for(int i=0;i<n;i++)
cin>>c[i];
dfs(0,-1);
cout<<dp[0][1]<<endl;
return 0;
}