题解 P6623 【[2020 年联考 A 卷] 树【暂无数据】】

· · 题解

省选救命题虽然大概率救不回来。

考虑根据每个点的儿子推出他的值。然后如果我们用一个数据结构去维护所有的儿子，那么容易发现我们需要支持四个操作：

然后你就可以去看这篇题解了。

凭借直接我们知道肯定是用 trie 去维护，然后你发现你不会第三个操作。

对于一个数来说加一就是把他最低位的一堆一变成零然后把最低的零变成一对吧。

所以你从低到高维护 trie，然后就交换一下左右儿子并在左儿子递归修改即可。

复杂度 1log，代码可以参考那篇题解。

upd：关于这个做法的复杂度证明：因为值域 O(n)，所以线段树合并的复杂度证明并不会被这个加一破坏掉，每个数还是最多被插一次。

所以我是被卡常了……哭。

upd：代码：

#include<algorithm>
#include<vector>
#include<cctype>
#include<cstdio>
using namespace std;
inline int readint(){
    int x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-'){
        f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=525010+5;
int n,v[maxn];
vector<int> ch[maxn];
struct node{
    int d;
    node* ch[2];
    int s,v;
    void pushup(){
        s=v=0;
        if(ch[0]){
            s+=ch[0]->s;
            v^=ch[0]->v;
        }
        if(ch[1]){
            s+=ch[1]->s;
            v^=(ch[1]->s&1)<<d^ch[1]->v;
        }
    }
    node(int d):d(d),s(0),v(0){
        ch[0]=ch[1]=0;
    }
    void insert(int x){
        if(d>25){
            s++;
            return;
        }
        if(x>>d&1){
            if(!ch[1]) ch[1]=new node(d+1);
            ch[1]->insert(x);
        }
        else{
            if(!ch[0]) ch[0]=new node(d+1);
            ch[0]->insert(x);
        }
        pushup();
    }
    void modify(){
        swap(ch[0],ch[1]);
        if(ch[0]) ch[0]->modify();
        pushup();
    }
};
node* merge(node* a,node* b){
    if(!a) return b;
    if(!b) return a;
    a->s+=b->s;
    a->v^=b->v;
    a->ch[0]=merge(a->ch[0],b->ch[0]);
    a->ch[1]=merge(a->ch[1],b->ch[1]);
    delete b;
    return a;
}
node* rt[maxn];
long long ans=0;
void dfs(int u){
    rt[u]=new node(0);
    for(int i=0;i<(int)ch[u].size();i++){
        int v=ch[u][i];
        dfs(v);
        rt[u]=merge(rt[u],rt[v]);
    }
    rt[u]->modify();
    rt[u]->insert(v[u]);
    ans+=rt[u]->v;
}
int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    n=readint();
    for(int i=1;i<=n;i++) v[i]=readint();
    for(int i=2;i<=n;i++) ch[readint()].push_back(i);
    dfs(1);
    printf("%lld\n",ans);
    return 0;
}