「联合省选 2020 A」树

按位考虑。

对于一个点来说，其儿子到其的距离是 /(dep_v-u/)。

那么其儿子做出的贡献是 /(V_v+dep_v-dep_u/)。

在模 /(2^{i+1}/) 的意义下若 /(2_i/le V_v+dep_v-dep_u< 2^{i+1}/) 则 /(v/) 会对 /(u/) 产生一个 /(2^i/) 的贡献。

也就是说，我们求出以 /(u/) 为根的子树中所有点的 /(V_v+dep_v/) 的桶并且对 /([2^i+dep_u.2^{i+1}+dep_u)/) 这个区间内做一个统计即可。

注意，这里的区间都应该是在模 /(2^{i+1}/) 的意义下的，而我们上述式子在代码中应该转换成模 /(2^{i+1}/) 意义下。具体细节看代码（也就是可能统计区间是分两段的，也就是 /([l,2^{i+1})/cup[1,r]/)，由于 /(V_v+dep_v/) 一定大于 /(dep_u/) ，所以 /([1,r]/) 这段区间是有意义的）

求出以 /(u/) 为根的子树中所有点权值的桶是一个经典问题，我们可以 dfs 一遍，然后将进入 /(u/) 和从 /(u/) 出去的桶做一个差分即可得到。

复杂度 /(O(n/log^2 V)/)。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = (1<<21)+5;
const int MX = (1<<21);
bool Small;
struct BIT
{
	#define lowbit(i) (i&(-i))
	int t[MAXN],mx;
	BIT(){memset(t,0,sizeof t);}
	void upd(int p,int x){for(int i=p;i<=mx;i+=lowbit(i))t[i]^=x;}
	ll que(int p){ll r=0;for(int i=p;i;i-=lowbit(i))r^=t[i];return r;}
	ll Q(int l,int r){return que(r)^que(l-1);}
}t[21];
vector <int> e[MAXN];
int n;
ll v[MAXN],val[MAXN],Ans;
bool Sunny;
void Calc(int p,int d)
{
	for(int i=0;i<=20;++i)
	{
		int l=(1<<i)+d,r=(1<<(i+1))+d-1;
		l=(l&((1<<i+1)-1))+1;r=(r&((1<<i+1)-1))+1;
		if(r<l)val[p]^=t[i].Q(l,1<<(i+1))^t[i].Q(1,r);
		else val[p]^=t[i].Q(l,r);
	}
}
void dfs(int p,int d)
{
	v[p]+=d;
	Calc(p,d);
	for(int i=0;i<=20;++i) t[i].upd((v[p]&((1<<i+1)-1))+1,(1<<i));
	for(int v:e[p]) dfs(v,d+1);
	Calc(p,d);
	Ans+=val[p];
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<=20;++i) t[i].mx=(1<<i+1);
	for(int i=1;i<=n;++i) scanf("%d",&v[i]);
	for(int i=2;i<=n;++i)
	{
		int fa;scanf("%d",&fa);
		e[fa].push_back(i);
	}
	dfs(1,0);
	printf("%lld/n",Ans);
	return 0;
}