洛谷10分记录

LOJ AC记录

What's wrong?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=6e5,MAX_V=6e5*100;
int readint()
{
	register int x=0;
	register char c=getchar();
	while(c<'-')c=getchar();
	for(;c>='0'&&c<='9';c=getchar())
		  x=x*10+c-'0';
	return x;
}
int N;

	static int mempool[MAX_N],mempoolsize;
	static int ch[MAX_V][2],fa[MAX_V];//sum ¡Á¨®¨º¡Â?Dxoro¨ª
	ll sum[MAX_V];
	static bool endcnt[MAX_V],cnt[MAX_V];
	static int allocate()
	{
		static int total=0;
		//if(mempoolsize>0)return mempool[mempoolsize--];
		return ++total;
	}
	static void destroy(int x)
	{
		mempool[++mempoolsize]=x;
		ch[x][0]=ch[x][1]=sum[x]=fa[x]=endcnt[x]=cnt[x]=0;
	}
	static void maintain(int u)
	{
		cnt[u]=cnt[ch[u][0]]^cnt[ch[u][1]]^endcnt[u];
		sum[u]=((sum[ch[u][0]]^sum[ch[u][1]])<<1)|cnt[ch[u][1]];
	}
	static void merge(int u,int v)
	{
		if(v==0)return;
		for(int k=0;k<2;k++)
			if(!ch[u][k])ch[u][k]=ch[v][k];
			else merge(ch[u][k],ch[v][k]);
		endcnt[u]^=endcnt[v];
		maintain(u);
		destroy(v);
	}
struct Trie{
	
	int rt;
	Trie(){rt=allocate();}
	void insert(int x)
	{
		if(rt==0)rt=allocate();
		int u=rt;
		while(x!=0)
		{
			bool v=x&1;
			if(!ch[u][v]){
				ch[u][v]=allocate();
				fa[ch[u][v]]=u;
			}
			u=ch[u][v];
			cnt[u]^=1;
			x>>=1;
		}
		endcnt[u]^=1;
		while(u!=0)
		{
			maintain(u);
			u=fa[u];
		}
	}
	void increace(int u)
	{
		swap(ch[u][0],ch[u][1]);
		if(endcnt[u]){
			if(!ch[u][1]){
				ch[u][1]=allocate();
				fa[ch[u][1]]=u;
			}
			endcnt[ch[u][1]]^=1;
			cnt[ch[u][1]]^=1;
			endcnt[u]=0;
		}
		if(ch[u][0])increace(ch[u][0]);
		maintain(u);
	}
	void increace()
	{
		increace(rt);
	}
	void merge(Trie tree)
	{
		::merge(rt,tree.rt);
	}
}trieasdasdadas;
int to[MAX_N],nxt[MAX_N],head[MAX_N];
void addedge(int u,int v)
{
	static int total=0;
	nxt[++total]=head[u];
	head[u]=total;
	to[total]=v;
}
ll ans;int val[MAX_N];
Trie dfs(int u)
{
	Trie tree;
	tree.insert(val[u]);
	for(int e=head[u];e!=0;e=nxt[e])
	{
		Trie t=dfs(to[e]);
		t.increace();
		tree.merge(t);
	}
	ans+=sum[tree.rt];
	return tree;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("stdin.txt", "r", stdin);
#endif
	int n=readint();
	for(int i=1;i<=n;i++)
		val[i]=readint();
	for(int i=2;i<=n;i++)
		addedge(readint(),i);
	dfs(1);
	printf("%lld",ans);
	return 0;
}