461B - Appleman and Tree - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5, MOD = 1e9 + 7;

int dp[maxn][2], c[maxn];
vector<int> adj[maxn];
//dp[u][c] = quantas maneiras ha de resolver o problema tal que a raiz (u)
// esta numa componente de soma c

int inv(int a){
	int rt = 1, xp = MOD-2;
	while(xp){
		if(xp&1) rt = rt*a%MOD;
		xp>>=1;
		a = a*a%MOD;
	}

	return rt;
}

void solve(int u){
	if(adj[u].size()==0){
		dp[u][1] = c[u];
		dp[u][0] = !c[u];
		return;
	}

	int total = 1;
	for(int v : adj[u]) solve(v), total = total*((dp[v][1]+dp[v][0])%MOD)%MOD;
	dp[u][c[u]] = total;
	//se meu valor eh x, entao eu posso n conectar com todos os 1's
	//e conectar com todos os 0's e meu valor continuara o mesmo

	if(!c[u])
		for(int v : adj[u])
			dp[u][1] = (dp[u][1]+(dp[v][1]*(total*inv((dp[v][1]+dp[v][0])%MOD)%MOD)%MOD)%MOD)%MOD;
	//se meu valor eh 0, eu posso conectar com cada 1 individualmente e
	//nao alterar minha soma para todos os outros filhos
}

int32_t main(){
	int n; cin >> n;
	for(int i = 1; i < n; i++){
		int a; cin >> a;
		adj[a].push_back(i);
	}
	for(int i = 0; i < n; i++) cin >> c[i];

	solve(0);

	cout << dp[0][1] << '\n';
}