描述
题解
树形DP,状态转移方程不是特别容易想。
我们先设置 dp[i][0/1] 表示以当前节点 i 为根的子树且包含该根的联通块儿的方案数,方案数划分为两部分,一部分是不包含黑色的方案数,另一种则包含一个黑色。
这样子我们可以分析出来联通块儿之间的关系,假设两个联通块儿
具体状态转移方程就不再多此一举了,直接看代码即可。这里我们需要用到乘法原理,至于为什么,我想不用多说了吧……需要注意的是,每一种的转移都要考虑连通和不连通两种,因为很明显的是,不管连不连通,只要结果合法,那就是不同的方案嘛~~~
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
int n;
int x[MAXN];
long long dp[MAXN][2];
vector<int> G[MAXN];
void dfs(int r, int pre)
{
if (x[r])
{
dp[r][1] = 1;
}
else
{
dp[r][0] = 1;
}
int sz = (int)G[r].size(), nt;
for (int i = 0; i < sz; i++)
{
nt = G[r][i];
if (pre != nt)
{
dfs(nt, r);
dp[r][1] = (dp[r][1] * (dp[nt][0] + dp[nt][1]) + dp[r][0] * dp[nt][1]) % MOD;
dp[r][0] = (dp[r][0] * (dp[nt][0] + dp[nt][1])) % MOD;
}
}
}
int main()
{
scanf("%d", &n);
int p;
for (int i = 1;i < n; i++)
{
scanf("%d", &p);
G[p].push_back(i);
G[i].push_back(p);
}
for (int i = 0;i < n; i++)
{
scanf("%d", x + i);
}
dfs(0, -1);
printf("%lld\n", dp[0][1]);
return 0;
}