感觉是那种，看到题就能猜到大概思路的题。
首先给题目条件增加限制：考虑 \(x_i\leq 7\) 的时候怎么做。这启示我们思考一个和值域相关的做法。
很容易想到一个树形 dp：设 \(dp_{u,i}\) 为在以 \(i\) 为根的子树中，\(u\) 所在连通块异或和为 \(i\) 时方案数与其他连通块各自的异或和之积的乘积。则有：
\[dp_{u,i\oplus j}+dp_{u,i}\times dp_{v,j}\to dp_{u,i\oplus j} \]\[dp_{u,i}\times dp_{v,j}\times j\to dp_{u,i} \]以树上背包的形式合并。
以上做法能得到 36pts。考虑怎样拓展至值域更大的情况。
异或具有很好的性质。可以考虑拆开每一位分别算。状态变为 \(dp_{u,i,0/1}\) 表示在以 \(i\) 为根的子树中，\(u\) 所在连通块异或和的第 \(i\) 位为 \(0/1\) 时方案数与其他连通块各自的异或和之积的乘积。
再来分析两种转移：第一种没太大变化，向两个数当前位的异或值转移。第二种则有一点变化。可以考虑乘法分配律暴力拆开，发现每个为 \(1\) 的位都会对当前位的 dp 值有贡献。所以便变成：
\[dp_{u,i,p\oplus q}+dp_{u,i,p}\times dp_{v,i,q}\to dp_{u,i,p\oplus q} \]\[dp_{u,i,p}\times dp_{v,j,1}\times 2^j\to dp_{u,i,p} \]这样就有 84pts 了。最后一个转移是 \(O(\log^2 V)\) 的，发现可以再用分配律合起来，就变成 \(O(\log V)\) 的了。总复杂度 \(O(n\log V)\)。
点击查看代码
int n,m,dp[N][64][2],f[64][2];
ll c[N];
int tot,head[N];
struct node{
int to,nxt;
}e[N<<1];
il void add(int u,int v){
e[++tot]={v,head[u]};
head[u]=tot;
}
il int Mod(int x,int y){
((x+=y)>=mod)&&(x-=mod);
return x;
}
void dfs(int u,int fa){
rep(i,0,62){
dp[u][i][(c[u]>>i)&1ll]=1;
}
go(i,u){
int v=e[i].to;
if(v==fa)
continue;
dfs(v,u);
int sum=0;
rep(j,0,62){
sum=Mod(sum,1ll*dp[v][j][1]*((1ll<<j)%mod)%mod);
}
mems(f,0);
rep(j,0,62){
rep(p,0,1){
rep(q,0,1){
f[j][p^q]=Mod(f[j][p^q],1ll*dp[u][j][p]*dp[v][j][q]%mod);
}
f[j][p]=Mod(f[j][p],1ll*dp[u][j][p]*sum%mod);
}
}
rep(j,0,62)rep(k,0,1){
dp[u][j][k]=f[j][k];
}
}
}
void Yorushika(){
scanf("%d",&n);
rep(i,1,n){scanf("%lld",&c[i]);}
rep(i,2,n){
int v;scanf("%d",&v);
add(v,i),add(i,v);
}
dfs(1,0);
int ans=0;
rep(i,0,62){ans=Mod(ans,1ll*dp[1][i][1]*((1ll<<i)%mod)%mod);}
printf("%d\n",ans);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}