heoi2020树

· · 题解

_ 01trie树合并 _

在考场上一直想用数据结构维护，还花了好长时间算 (a+1)^(b+1)，现在看来当时好像在犯傻。。。。。。。。

异或有个神奇的工具是 01trie 树，此题就用此种方式解决。

  1. 插入操作，显然。
  2. 计算子树异或和，合并 01trie 树，记录 size，偶数为 0，奇数为 1，即可实现。
  3. 整体加 1,也是此题关键所在。偶数则直接加 1,更新答案，奇数则进位，并更新， 注意此处更新只在 size&1==1 时才进行。具体操作交换左右儿子，沿 0 向下一位进位。因为现在的 0 是之前的 1 换过来的，这一位加 1 后还要考虑向下一位进位。

就这样完美解决，妙哉。 code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ans,ch[525011*21][2],val[525011],xval[525011],n,head[525011],size[525011*21],root[525011],cnt,tot;
struct ccc
{int to,next;}bian[525011];
inline void add(int u,int v)
{   bian[++tot].to=v;
    bian[tot].next=head[u];
    head[u]=tot;
}
inline int ins(int x,int sum)
{   if(!x)x=++cnt;
    int ddd=x;
    for(int i=1;i<=21;++i)
    {   if(!ch[ddd][(sum>>(i-1))&1])ch[ddd][(sum>>(i-1))&1]=++cnt;
        ddd=ch[ddd][(sum>>(i-1))&1];++size[ddd];
    }
    return x;
}
inline void update(int x)
{   int rt=root[x];
    for(int i=1;i<=21;++i)
    {   if(size[ch[rt][1]]&1)xval[x]^=(1<<(i-1));
        swap(ch[rt][1],ch[rt][0]);
        if(size[ch[rt][1]]&1)xval[x]^=(1<<(i-1));
        rt=ch[rt][0];
        if(!rt)break;
    }
}
inline int merge(int x,int y)
{   if(!x or !y)return x+y;
    size[x]+=size[y];
    ch[x][0]=merge(ch[x][0],ch[y][0]);
    ch[x][1]=merge(ch[x][1],ch[y][1]);
    return x;
}
inline void dfs(int x)
{   for(int i=head[x];i;i=bian[i].next)
    {   int v=bian[i].to;
        dfs(v);
        update(v);
        root[x]=merge(root[x],root[v]);
        xval[x]^=xval[v];
    }
    root[x]=ins(root[x],val[x]);
    xval[x]^=val[x];
    ans+=xval[x];
}
signed main()
{   ///freopen("c.in","r",stdin);
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&val[i]);
    for(int i=2;i<=n;++i)
    {   int u;
        scanf("%lld",&u);
        add(u,i);
    }
    dfs(1);
    printf("%lld\n",ans);
}