cf461 B. Appleman and Tree

题意：

有 n 个节点的树，节点为黑色或白色。现在可以从中删去若干条边，使得剩下的每个连通块恰有一个黑色节点。问有多少种删边方案。

思路：

树形dp，\(f(u,0/1)\) 表示 \(u\) 所在的连通块中黑点的数量。

答案为 \(f(1,1)\)

ll n, a[N], f[N][2];

void dfs(int u, int fa) {
    f[u][a[u]] = 1;
    for(int v : G[u])
        if(v != fa) dfs(v, u);

    ll t0 = f[fa][0], t1 = f[fa][1];
    f[fa][0] = t0 * (f[u][0] + f[u][1]) % mod;
    f[fa][1] = (t0 * f[u][1] + t1 * (f[u][0] + f[u][1])) % mod;
}

signed main() {
    iofast;
    cin >> n;
    for(int i = 2, x; i <= n; i++)
        cin >> x, G[++x].pb(i), G[i].pb(x);
    for(int i = 1; i <= n; i++) cin >> a[i];

    dfs(1, 0);
    cout << f[1][1];
}