[DS记录] P6623 [省选联考 2020 A 卷] 树-526互联

\(\rm Trie\) 树的一些牛逼应用

异或和是可以用 \(\rm 01-Trie\) 维护的。我们发现对于一个点 \(x\)，需要需要维护 \(x\) 子树的所有点的异或和，这可以理解成 \(\rm Trie\) 树的合并。同时有一个 \(d(y,x)\) 的存在，其实考虑 \(\rm dfs\) 的过程，相当于先合并所有子节点的 \(\rm Trie\) 树后，对所有数 \(+1\)。再插入 \(val_x\)

因此，我们的 \(\rm Trie\) 树需要有以下的功能：

维护异或和
插入一个数
合并两个子树
整棵树所有的数 \(+1\)

前两个操作是基本的，将数从低位到高位插入，每个节点 \(p\) 维护 \(ch[p][2],siz[p],dat[p]\)。合并类似线段树合并。整棵树 \(+1\) 的操作其实相当于从低位到高位找第一个出现的 \(0\)，然后把 \(0\) 变 \(1\)，低位的 \(1\) 全部变 \(0\)。对应到字典树上相当于交换左右儿子，然后递归 \(ch[p][0]\)。注意因为有 \(+1\)，所以会导致进位，因此我们在一开始插入一个数时就完整地插入 \(21\) 位，这样就不会溢出

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=525020,NN=21*525010+10,M=21;

int n,val[N],rt[N],tot;
int ch[NN][2],dat[NN],siz[NN];
LL ans;
vector <int> g[N];

void maintain(int p)
{
	dat[p]=siz[p]=0;
	if(ch[p][0])
	{
		siz[p]+=siz[ch[p][0]];
		dat[p]^=dat[ch[p][0]]<<1;
	}
	if(ch[p][1])
	{
		siz[p]+=siz[ch[p][1]];
		dat[p]^=(dat[ch[p][1]]<<1)|(siz[ch[p][1]]&1);
	}
}

void insert(int &p,int v,int dep)
{
	if(!p)
		p=++tot;
	if(dep==M)
	{
		siz[p]++;
		return;
	}
	
	int t=v&1;
	insert(ch[p][t],v>>1,dep+1);
	maintain(p);
}

void add(int p)
{
	swap(ch[p][0],ch[p][1]);
	if(ch[p][0])
		add(ch[p][0]);
	maintain(p);
}

int merge(int p,int q)
{
	if(!p)
		return q;
	if(!q)
		return p;
	siz[p]+=siz[q];
	dat[p]^=dat[q];
	ch[p][0]=merge(ch[p][0],ch[q][0]);
	ch[p][1]=merge(ch[p][1],ch[q][1]);
	maintain(p);
	return p;
}

void dfs(int x)
{
	for(auto y:g[x])
	{
		dfs(y);
		rt[x]=merge(rt[x],rt[y]); 
	} 
	
	add(rt[x]);
	insert(rt[x],val[x],0);
	ans+=(LL)dat[rt[x]];
}

int main()
{	
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&val[i]);
	for(int i=2; i<=n; i++)
	{
		int fa;
		scanf("%d",&fa);
		g[fa].push_back(i);
	}
	
	dfs(1);
	
	printf("%lld",ans);
	
	return 0;
}