cnyz's Blog

• https://www.luogu.com.cn/problem/P6018

发现修改有一个是与距离为 $1$的所有节点有关，询问也是如此，考虑怎样维护这个玩意。

显然可以考虑从距离为 $1$ 下手，距离为 $1$，意味着要么是儿子，要么是父亲。

所以，单独处理父亲，用某个神奇的数据结构维护儿子的异或和，支持全局加一、删除节点、加入节点即可。

什么数据结构呢？$01$ Trie！

我们维护两个量，一个 $w$，一个 $xorv$，$w$ 表示当前节点的数的个数，考虑怎样自底向上更新。

有：

$w_p=w_{ls}+w_{rs}\\xorv_p=xorv_{ls}\times 2+xorv_{rs}\ \text{or}\ (w_{rs}\ \text{and}\ 1)$

而全局加呢，发现这玩意比较 NB，为什么加的是 $1$ 啊？

加了一，不就是从低位到高位找到第一个 $0$，然后把后面的 $1$ 全变成 $0$ 吗？所以一路递归下去找第一个 $0$，然后把两端儿子交换一下即可。

没了么？还有！

注意到我们只针对儿子进行了处理，加只是在 Trie 树上加的，考虑怎样处理。

第二个问题很好解决，对每个点打个标记，表示自己的儿子要加多少。

而父亲呢，如果父亲改了，即 $+1$ 操作 ，修改爷爷所在的 Trie 树，如果父亲没改，只改了自身，修改父亲所在的 Trie 树。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int N=5e5,H=21;
vector<int> e[N+2];
int val[N+2],fa[N+2],laz[N+2];
int rt[N+2],ch[N*25+2][2],w[N*25+2],xorv[N*25+2],cnt=0;
void maintain(int p) {
	w[p]=xorv[p]=0;
	if(ch[p][0]) {
		w[p]+=w[ch[p][0]];
		xorv[p]^=xorv[ch[p][0]]<<1;
	}
	if(ch[p][1]) {
		w[p]+=w[ch[p][1]];
		xorv[p]^=(xorv[ch[p][1]]<<1)|(w[ch[p][1]]&1);
	}
}
int mknode() {
	++cnt;ch[cnt][1]=ch[cnt][0]=w[cnt]=xorv[cnt]=0;
	return cnt;
}
void insert(int &p,int x,int dep) {
	if(!p) p=mknode();
	if(dep>H) {w[p]++;return;}
	insert(ch[p][x&1],x>>1,dep+1);
	maintain(p);
}
void erase(int &p,int x,int dep) {
	if(dep>H) {w[p]--;return;}
	erase(ch[p][x&1],x>>1,dep+1);
	maintain(p);
}
void addall(int p) {
	swap(ch[p][0],ch[p][1]);
	if(ch[p][0]) addall(ch[p][0]);
	maintain(p);
}
int n,m,root=1;
void dfs(int x,int f) {
	fa[x]=f;
	for(auto i:e[x])
		if(i!=f) dfs(i,x);
}
int get(int x) {return (fa[x]==-1?0:laz[fa[x]])+val[x];}
void solve() {
	scanf("%d %d",&n,&m);
	for(int i=1;i<n;i++) {
		int x,y;
		scanf("%d %d",&x,&y);
		e[x].push_back(y);e[y].push_back(x);
	}
	dfs(root,-1);
	for(int i=1;i<=n;i++) {
		scanf("%d",&val[i]);
		if(fa[i]!=-1) insert(rt[fa[i]],val[i],0);
	}
	while(m--) {
		int op,x,v;
		scanf("%d %d",&op,&x);
		if(op==1) {
			laz[x]++;
			if(x!=root) {
				if(fa[fa[x]]!=-1) erase(rt[fa[fa[x]]],get(fa[x]),0);
				val[fa[x]]++;
				if(fa[fa[x]]!=-1) insert(rt[fa[fa[x]]],get(fa[x]),0);
			}
			addall(rt[x]);
		}
		if(op==2) {
			scanf("%d",&v);
			if(fa[x]!=-1) erase(rt[fa[x]],get(x),0);
			val[x]-=v;
			if(fa[x]!=-1) insert(rt[fa[x]],get(x),0);
		}
		if(op==3) {
			int res=xorv[rt[x]];
			res^=get(fa[x]);
			printf("%d\n",res);
		}
	}
}
int main() {
	int t=1;
	while(t--) solve();
}

实现细节/Trick

• 本题不卡常。
• 注意出现了一个限高的操作，这是为了使维护 $w$ 的时候更加好写。
• 维护周围节点时，考虑将父亲抽离，单个统计父亲贡献，整体统计儿子贡献。