Luogu

LOJ

分析

考虑每个节点用一个数据结构维护子树中所有点的信息。

则我们需要支持插入、合并、全局加 $1$、求全局异或和四个操作。

可以用 01-Trie 来维护。前面两个操作是基本操作。

考虑全局加 $1$。如果是一个偶数，它的最低位会变为 $1$；否则它的最低位会变成 $0$，然后给次低位加上 $1$，仍然可以根据次低位讨论。放到 Trie 树上就是从低到高枚举每一位，交换当前节点的左右儿子，然后往 $0$ 对应的儿子递归下去。

全局异或和在上面三个操作的同时维护一下即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=525010+10;

int n,v[N],val[N]; ll ans=0;
vector<int> E[N];

#define ls(o) ch[o][0]
#define rs(o) ch[o][1]
int rt[N],ch[N*21][2],sz[N*21],tot=0;
void insert(int u,int w) {
    if (!rt[u]) rt[u]=++tot;
    int o=rt[u]; ++sz[o];
    for (int i=0;i<=20;++i) {
        int k=(w>>i)&1;
        if (!ch[o][k]) ch[o][k]=++tot;
        o=ch[o][k],++sz[o];
    }
}
void modify(int u) {
    int o=rt[u];
    for (int i=0;i<=20;++i) {
        if (sz[rs(o)]&1) val[u]^=1<<i;
        swap(ls(o),rs(o));
        if (sz[rs(o)]&1) val[u]^=1<<i;
        o=ls(o); if (!o) break;
    }
}
int merge(int x,int y) {
    if (!x||!y) return x|y;
    sz[x]+=sz[y];
    ls(x)=merge(ls(x),ls(y));
    rs(x)=merge(rs(x),rs(y));
    return x;
}

void dfs(int u) {
    for (int v:E[u])
        dfs(v),modify(v),rt[u]=merge(rt[u],rt[v]),val[u]^=val[v];
    insert(u,v[u]),val[u]^=v[u],ans+=val[u];
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) v[i]=read();
    for (int i=2;i<=n;++i) E[read()].emplace_back(i);
    dfs(1); printf("%lld\n",ans);
    return 0;
}