C++14(g++5.4) 解法, 执行用时: 388ms, 内存消耗: 16224K, 提交时间: 2020-03-17 13:52:33

#include <bits/stdc++.h>
using namespace std;
 
const int N = 500003, mod = 1004535809;
typedef long long ll;
ll dp[N][2];
struct Edge {
  int v, nxt;
} G[N]; int head[N], a[N], M;
void adde(int u, int v) {
  G[++head[0]] = (Edge) {v, head[u]}; head[u] = head[0];
}
void dfs(int u) {
  dp[u][0] = 1;
  ll dpu0, dpu1;
  for (int i = head[u]; i; i = G[i].nxt) {
    int v = G[i].v;
    dfs(v);
    a[u] ^= a[v];
    dpu0 = dp[u][0], dpu1 = dp[u][1];
    dp[u][0] = (dpu0 * dp[v][0] + dpu1 * dp[v][1]) % mod;
    dp[u][1] = (dpu0 * dp[v][1] + dpu1 * dp[v][0]) % mod;
  }
  dpu0 = dp[u][0], dpu1 = dp[u][1];
  if (u == 1) cout << (dpu0 * (a[u] == M) + dpu1 * (a[u] == 0)) % mod;
  //和父亲的边
  if (a[u] == 0) (dp[u][0] += dpu1) %= mod;
  if (a[u] == M) (dp[u][1] += dpu0) %= mod;
}
int main() {
  int n;
  scanf("%d%d", &n, &M);
  for (int u, i = 2; i <= n; i++) scanf("%d", &u), adde(u, i);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  dfs(1);
  return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 379ms, 内存消耗: 33984K, 提交时间: 2023-07-29 23:54:57

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define PII pair<int,int>
const int N=5e5+5,mod=1004535809;int n,m;
vector<int>son[N];
ll a[N],f[N][2];ll ans=0;
void dfs(int u){	
	f[u][0]=1;
	for(auto v:son[u]){
		dfs(v);
		a[u]^=a[v];
		ll f0=f[u][0],f1=f[u][1];
		f[u][1]=(f1*f[v][0]+f0*f[v][1])%mod;
		f[u][0]=(f0*f[v][0]+f1*f[v][1])%mod;
	}
	ll f1=f[u][1],f0=f[u][0];
	if(u==1)ans=(ans+f0*(a[u]==m))+f1*(a[u]==0);
	if(a[u]==m)f[u][1]=(f[u][1]+f0)%mod;
	if(a[u]==0)f[u][0]=(f[u][0]+f1)%mod;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++){
		int fa;
		scanf("%d",&fa);
		son[fa].push_back(i);
	}
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	dfs(1);
	printf("%d\n",ans%mod);
}