heoi2020树

_ _01trie树合并 _ _

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

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

插入操作，显然。
计算子树异或和，合并 01trie 树，记录 size，偶数为 0，奇数为 1，即可实现。
整体加 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);

}

巴特西

heoi2020树

_ _01trie树合并 _ _

最新文章

热门文章