自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:00:03，当前版本为作者最后更新于2024-07-06 17:24:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

一眼丁真，鉴定为：不会写 Splay。

考虑本题本质上是一个阶梯博弈 + 巴什博弈。

那么我们认为一个节点的实际石子个数为 $a_u \bmod (m+1)$，统计节点 $u$ 的子树中，距离它的长度为奇数的节点的实际石子个数的异或和。

在动态维护 LCT 的过程中，如果新增一个节点或者修改一个节点，把它到根这条路径上所有点都异或上新增的值。

每个点要开两个值，分别维护深度为奇数的点的异或和与深度为偶数的点的异或和。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,m,q,a[MAXN],dep[MAXN],lstans;
vector<int> G[MAXN];
struct Node {int s[2],fa,x0,x1;}t[MAXN];
struct Tag {int tg0,tg1,flp;}tag[MAXN];
void assign(int u,Tag tg) {
	if(tg.flp) swap(t[u].s[0],t[u].s[1]),tag[u].flp^=1;	
	return t[u].x0^=tg.tg0,t[u].x1^=tg.tg1,tag[u].tg0^=tg.tg0,tag[u].tg1^=tg.tg1,void();
}
void push_down(int u) {return assign(t[u].s[0],tag[u]),assign(t[u].s[1],tag[u]),tag[u]={0,0,0},void();}
void push_up(int u) {return ;}
int is_root(int u) {return u!=t[t[u].fa].s[0]&&u!=t[t[u].fa].s[1];}
int get(int u) {return u==t[t[u].fa].s[1];}
void rotate(int u) {
	int fa=t[u].fa,s=get(u),op=get(fa);
	if(!is_root(fa)) t[t[fa].fa].s[op]=u;t[u].fa=t[fa].fa;
	t[t[u].s[s^1]].fa=fa,t[fa].fa=u,t[fa].s[s]=t[u].s[s^1],t[u].s[s^1]=fa;
	return ;
}
void PUSH_DOWN(int u) {if(!is_root(u)) PUSH_DOWN(t[u].fa);return push_down(u),void();}
void splay(int u) {PUSH_DOWN(u);for(int f=t[u].fa;f=t[u].fa,!is_root(u);rotate(u)) if(!is_root(f)) rotate(get(u)==get(f)?f:u);return ;}
int access(int u) {int lst=0;while(u) splay(u),t[u].s[1]=lst,lst=u,u=t[u].fa;return lst;}
void make_root(int u) {return assign(access(u),{0,0,1}),void();}
void link(int u,int v) {return make_root(u),splay(u),t[u].s[1]=v,t[v].fa=u,void();}
void dfs(int u,int f) {
	dep[u]=dep[f]^1;
	if(f) {
		int rt;
		link(f,u),make_root(1),rt=access(u);
		if(dep[u]) assign(rt,{0,a[u],0});
		else assign(rt,{a[u],0,0});
	}
	for(auto v:G[u]) if(v!=f) dfs(v,u);
	return ;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	ffor(i,1,n) cin>>a[i],a[i]%=m+1;
	ffor(i,1,n-1) {int u,v;cin>>u>>v,G[u].push_back(v),G[v].push_back(u);}
	dfs(1,0);
	cin>>q;
	while(q--) {
		int op;
		cin>>op;
		if(op==1) {
			int u,val;
			cin>>u,u^=lstans;
			PUSH_DOWN(u);
			if(dep[u]) val=t[u].x0;
			else val=t[u].x1;
			if(val) cout<<"Yes\n",lstans++;
			else cout<<"No\n";
		}
		if(op==2) {
			int x,y,rt;
			cin>>x>>y,x^=lstans,y^=lstans,y%=m+1;
			make_root(1),rt=access(x);
			if(dep[x]) assign(rt,{0,a[x]^y,0});
			else assign(rt,{a[x]^y,0,0});
			a[x]=y;
		}
		if(op==3) {
			int u,v,x,rt;
			cin>>u>>v>>x,u^=lstans,v^=lstans,x^=lstans;
			dep[v]=dep[u]^1,a[v]=x%(m+1);
			link(u,v),make_root(1),rt=access(v);
			if(dep[v]) assign(rt,{0,a[v],0});
			else assign(rt,{a[v],0,0});	
		}
	}
	return 0;
}