本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-03 21:34:55

考虑按位计算贡献，先考虑链的情况。考虑倍增，设 $f_{i,k}$ 表示 $[i,i+2^k)$ 区间的答案。转移时先累加两个小区间的贡献，另外后半部分的第 $(k-1)$ 位要异或 $1$，因此设 $g_{i,k}$ 表示前 $i$ 个数第 $k$ 位若异或 $1$ 会产生的总变化量。统计时若其该位为 $1$ 则贡献 $-1$，否则贡献 $1$。通过差分计算变化量，最终转移为 $f_{i,k}=f_{i,k-1}+f_{i+2^{k-1},k-1}+2^{k-1}\times(g_{i+2^k-1}-g_{i+2^{k-1}-1})$。统计答案时一直向后跳并累加即可。

考虑把这东西搬到树上，但由于子树内在某一层上的点不止一个，只能在 $i$ 节点本身上记录信息。所以设 $f_{i,j,k}$ 表示 $i$ 子树内深度在 $[d_i+j,d_i+j+2^k)$ 内所有点的贡献和。可以发现这个 $(i,j)$ 很能长链剖分，重儿子直接继承，轻儿子对应位置直接累加。但是这样没有计算 $f_{i,0}$，考虑怎么计算这个。

那么先把 $a_i$ 加到 $f_{i,0}$ 里。假如从子树 $v$ 给 $f_{i,0}$ 更新，设 $s_k$ 表示 $v$ 子树内对 $f_{i,0,k}$ 的贡献，有 $s_0=0$。发现 $s_k$ 可以用 $s_{k-1}$ 拼上 $f_{v,2^{k-1}-1,k-1}$ 得到，这里的式子应该和链的情况一样，实际实现时由于 $s_k$ 只从 $s_{k-1}$ 转移，开一个变量，一直更新就行。

那么问题就在于还需要一个记录贡献变化量的数组 $g$ 来辅助更新。链上我们是用前缀和维护的，但是树上长剖不好搞前缀和，所以考虑转而计算后缀和。具体地设 $g_{i,j,k}$ 表示 $i$ 子树内深度不低于 $d_i+j$ 的所有点权第 $k$ 位若异或 $1$ 会产生的总变化量，这就可以直接对应位累加了，只需要在 $g_{i,0}$ 上额外加入 $a_i$ 的贡献即可。

所有的转移和统计答案都跟链上类似，把每个询问扔到对应节点上处理即可。只是要格外注意在 $g$ 上差分时不能超出当前节点的管辖范围，有比较多的细节。时间复杂度 $O((n+q)\log n)$。

#include<iostream>
#include<vector>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int N=1e6+10;
const int K=20+3;
int n,q,v[N],d[N],son[N]; ll res[N];
vector <int> e[N];
vector <pii> a[N];
struct nod{ll f[K],g[K];}temp[N],*f[N],*cur=temp;
void dfs(int u)
{
	d[u]=0;
	for(int v:e[u])
	{
		dfs(v),d[u]=max(d[u],d[v]);
		if(d[v]>d[son[u]]) son[u]=v;
	}
	d[u]++;
}
void merg(int u,int v)
{
	for(int j=0;j<20;j++) f[u][0].g[j]+=f[v][0].g[j];
	ll s=0;
	for(int p=0,k=1;k<20;p+=(1<<(k-1)),k++)
	{
		if(p<d[v]) s+=f[v][p].f[k-1]+(1<<(k-1))*f[v][p].g[k-1];
		if(p+(1<<(k-1))<d[v]) s-=(1<<(k-1))*f[v][p+(1<<(k-1))].g[k-1];
		f[u][0].f[k]+=s;
	}
}
void dfsb(int u)
{
	for(int j=0;j<20;j++) f[u][0].f[j]=v[u],f[u][0].g[j]=(((v[u]>>j)&1)?-1:1);
	if(son[u]) f[son[u]]=f[u]+1,dfsb(son[u]),merg(u,son[u]);
	for(int v:e[u]) if(v!=son[u])
	{
		f[v]=cur,cur+=d[v],dfsb(v),merg(u,v);
		for(int j=0;j<d[v];j++) for(int k=0;k<20;k++) 
			f[u][j+1].f[k]+=f[v][j].f[k],f[u][j+1].g[k]+=f[v][j].g[k];
	}
	for(pii te:a[u])
	{
		int x=min(te.first,d[u]-1),id=te.second;
		for(int p=0,k=19;k>=0;k--)
		{
			if(p+(1<<k)-1>x) continue;
			res[id]+=f[u][p].f[k],p+=(1<<k);
			if(p<d[u]) res[id]+=(1<<k)*f[u][p].g[k];
			if(x+1<d[u]) res[id]-=(1<<k)*f[u][x+1].g[k];
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n,d[0]=-1;
	for(int i=1;i<=n;i++) cin>>v[i];
	for(int i=2,x;i<=n;i++) cin>>x,e[x].push_back(i);
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		int x,k; cin>>x>>k;
		a[x].push_back({k,i});
	}
	dfs(1),f[1]=cur,cur+=d[1],dfsb(1);
	for(int i=1;i<=q;i++) cout<<res[i]<<'\n';
	return 0;
}