[被踩计划] 题解 [省选联考 2020 A 卷] 树

为什么叫被踩记录呢？因为感觉自己之前真的是太菜了，打算把之前联赛等考过的题目做一做，看看自已以前有多菜，所以取名叫被踩记录。

题目分析

列个表先：

不难发现，对于二进制下的第 (i) 位，如果每次加一，每隔 (2^i-1) 位这一位就会改变（由 (0) 到 (1) 或由 (1) 到 (0) ），我们可以考虑建 (log_2 n) 棵森林，其中第 (i(iin [0,log_2 n-1])) 棵森林中点 (x) 的父亲是原来点 (x) 的 (2^i) 级祖先，相当于是对于每一位分开考虑，那么此时该位会发生修改的其实就是这一位对应的那棵森林中 (x) 的所有祖先，这就是很基础的树上差分了，时间复杂度 (mathcal O(nlog_2n)) 。

怎么说呢，果然自己当时还是太菜了。

参考代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
	static char c;static int f;
	for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
	static char q[65];int cnt=0;
	if(x<0)pc('-'),x=-x;
	q[++cnt]=x%10,x/=10;
	while(x)
		q[++cnt]=x%10,x/=10;
	while(cnt)pc(q[cnt--]+'0');
}
const int maxn=550005;
int val[maxn],son[maxn],bro[maxn];
void qwq(int u,int v){
	bro[v]=son[u],son[u]=v;
}
int pa[maxn][21],f[maxn][21],lav[maxn];
long long ans;
void dfs(int u,int dp=0){
	for(int i=1;(1<<i)<=dp;++i)
		pa[u][i]=pa[pa[u][i-1]][i-1];
	lav[u]=val[u];
	for(int v=son[u];v;v=bro[v]){
		pa[v][0]=u;dfs(v,dp+1);lav[u]^=lav[v];
	}
	for(int i=0;i<21;++i)if(f[u][i]){
		lav[u]^=1<<i;f[pa[u][i]][i]^=1;
	}
	int no=pa[u][0];f[no][0]^=1;
	for(int i=0;i<20;++i){
		int o=(val[u]&1)^1;val[u]>>=1;
		if(o)no=pa[no][i];f[no][i+1]^=1;
	}
	ans+=lav[u];
}
int main(){
	int n;read(n);
	for(int i=1;i<=n;++i)read(val[i]);
	for(int i=2;i<=n;++i){
		int p;read(p);qwq(p,i);
	}
	dfs(1);write(ans),pc('
');
	return 0;
}