前言

题解的解法的赋初值是真没看懂..看了大佬的代码顺便问了大佬数组的含义才懂的这个题..

感觉这题对我来说应该算是有点难吧...

思路

首先可以知道为根的只有当子树的异或和为才有答案.
其他情况是没有答案的,所以我们可以重构一下树,将树中异或和为的点存起来.
假如为,答案显然是.
假如非,那么就需要跑树形了.
我们定义表示到了这个节点,的连通块的异或和为的方案数.
很显然的初值是假如这个点标记为,那么为.
否则这个点的值就是,那么为.
然后通过子树进行转移.
显然:

.

.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1004535809;
const int N=5e5+5;
ll n,M,w[N],id;
ll f[N][2],dp[N][2];
vector<int>g[N];
vector<int>G[N];
bool flag[N];
void dfs1(int u)
{
    for(int v:g[u])
    {
        dfs1(v);
        if(w[v]!=M) w[u]^=w[v];
    }
}

void dfs2(int u,int root)
{
    if(w[u]==0)
    {
        G[root].push_back(++id);
        flag[id]=true;
        root=id;
    }
    else if(w[u]==M)
    {
        G[root].push_back(++id);
        root=id;
    }
    for(int v:g[u])
        dfs2(v,root);
}

ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)    res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void dfs3(int u)
{
    if(flag[u])    f[u][0]=1;
    else        f[u][1]=1;
    for(int v:G[u])
    {
        dfs3(v);
        dp[u][0]=(f[u][0]*f[v][0]%mod+f[u][1]*f[v][1]%mod+f[u][0]*f[v][1]%mod)%mod;
        dp[u][1]=(f[u][1]*f[v][0]%mod+f[u][1]*f[v][1]%mod+f[u][0]*f[v][1]%mod)%mod;
        f[u][0]=dp[u][0],f[u][1]=dp[u][1];
    }
}

int main()
{
    scanf("%lld%lld",&n,&M);
    for(int i=1;i<n;i++)
    {
        int u;
        scanf("%d",&u);
        g[u].push_back(i+1);
    }
    for(int i=1;i<=n;i++)    scanf("%lld",&w[i]);
    dfs1(1);
    if(w[1]!=M&&w[1]!=0)
    {
        puts("0");
        return 0;
    }
    dfs2(1,0);
    if(M==0)
    {
        printf("%lld\n",qp(2,id-1));
        return 0;
    }
    dfs3(1);
    printf("%lld\n",f[1][1]);
    return 0;
}