自动搬运

查看原文

来自洛谷，原作者为

	Miss_SGT **

搬运于2025-08-24 22:33:26，当前版本为作者最后更新于2025-07-31 11:19:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

螳臂题面，“什么都不做”指颜色也不染。但开头就直接说染成蓝色。

补充之前题解的内容。

题目上的“出现次数为奇数”和 $p$ 的数据范围就差把 bitset 写题目上了。上线段树，除了操作 $3$ 其他都是容易的：循环位移、单修、异或。

发现操作 $3$ 很搞笑，如果我们刚开始把一个点的儿子从小到大排序来跑 dfs 序，则操作 $3$ 只会改变兄弟的子树大小，除此之外全部不变。所以我们可以用 set 维护一个点儿子的集合，操作一个点时，就在其父亲的 set 里找前驱，改变前驱的子树大小，再从 set 删除当前点就行。于是是在线的。

注意预处理 $i^k$。注意 bitset 左移溢出 $p$ 的部分需要消掉，不然后面可能会右移回来。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=998244353;
int n,q,P,k,a[N],w[N],f[N];
inline int pw(int x,int y){
	int ans=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ans=1ll*ans*x%mod;
	return ans;
}
set<int> S[N];
int dfn[N],low[N],idx,xl[N];
void dfs(int p,int fa){
	if(f[p]=fa) S[p].erase(fa);
	xl[dfn[p]=++idx]=p;
	for(int v:S[p]) dfs(v,p);
	low[p]=idx;
}
bitset<500> base;
struct Tree{
	int tag;
	bitset<500> S;
}t[1<<18];
#define mid ((l+r)>>1)
void build(int p,int l,int r){
	if(l==r){
		t[p].S[a[xl[l]]]=1;
		return;
	}
	build(2*p,l,mid),build(2*p+1,mid+1,r);
	t[p].S=t[2*p].S^t[2*p+1].S;
}
inline void ins(int p,int v){
	(t[p].tag+=v)%=P;
	t[p].S=((t[p].S<<v)&base)|(t[p].S>>(P-v));
}
inline void pushdown(int p){
	if(t[p].tag){
		ins(2*p,t[p].tag);
		ins(2*p+1,t[p].tag);
		t[p].tag=0;
	}
}
void change(int p,int l,int r,int lt,int rt,int v){
	if(lt<=l&&r<=rt) return ins(p,v),void();
	pushdown(p);
	if(lt<=mid) change(2*p,l,mid,lt,rt,v);
	if(mid<rt) change(2*p+1,mid+1,r,lt,rt,v);
	t[p].S=t[2*p].S^t[2*p+1].S;
}
void change(int p,int l,int r,int x,int v){
	if(l==r){
		t[p].S.reset();
		t[p].S[v]=1;
		return;
	}
	pushdown(p); 
	if(x<=mid) change(2*p,l,mid,x,v);
	else change(2*p+1,mid+1,r,x,v);
	t[p].S=t[2*p].S^t[2*p+1].S;
}
bitset<500> query(int p,int l,int r,int lt,int rt){
	if(lt<=l&&r<=rt) return t[p].S;
	pushdown(p);
	if(lt<=mid&&mid<rt) return query(2*p,l,mid,lt,rt)^query(2*p+1,mid+1,r,lt,rt);
	return lt<=mid?query(2*p,l,mid,lt,rt):query(2*p+1,mid+1,r,lt,rt);
}
int main(){
	read(n),read(q),read(P),read(k);
	for(int i=0;i<P;++i) w[i]=pw(i,k);
	for(int i=0;i<P;++i) base[i]=1;
	for(int i=1;i<=n;++i) read(a[i]);
	for(int i=1;i<n;++i){
		int x,y;
		read(x),read(y);
		S[x].insert(y);
		S[y].insert(x); 
	}
	dfs(1,0);
	build(1,1,n);
	while(q--){
		int op,x;
		read(op),read(x);
		if(op==1){
			int v;read(v);
			change(1,1,n,dfn[x],low[x],v);
		}
		if(op==2){
			int v;read(v);
			change(1,1,n,dfn[x],v);
		}
		if(op==3){
			if(x==1) continue;
			auto it=S[f[x]].find(x);
			if(it!=S[f[x]].begin()) low[*(--it)]=low[x],S[f[x]].erase(x);
		}
		if(op==4){
			auto s=query(1,1,n,dfn[x],low[x]);
			long long ans=0;
			for(int i=0;i<P;++i) if(s[i]) ans+=w[i];
			print(ans%mod),pc('\n');
		}
	}
	flush();
	return 0;
}