19pts 求助

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,r_id,p,cnt;
int w[N],dep[N],sz[N],fa[N],hs[N],tp[N],nw[N],id[N],lz[N<<2],t[N<<2];
vector<int> g[N]; 
int ls(int o){return o<<1;}
int rs(int o){return o<<1|1;}
void push_up(int o){
	t[o]=(t[o]+t[ls(o)]+t[rs(o)])%p;
}
void f(int s,int e,int o,int x){
	t[o]=(t[o]+1ll*(e-s+1)*x%p)%p;
	lz[o]=(lz[o]+x)%p;
}
void build(int s=1,int e=n,int o=1){
	if (s==e){
		t[o]=nw[s]%p;
		return;
	}
	int mid=(s+e)>>1;
	build(s,mid,ls(o));
	build(mid+1,e,rs(o));
	push_up(o);
}
void push_down(int s,int e,int o){
	if (!lz[o])return;
	int mid=(s+e)>>1;
	f(s,mid,ls(o),lz[o]);
	f(mid+1,e,rs(o),lz[o]);
	lz[o]=0;
}
void update(int l,int r,int x,int s=1,int e=n,int o=1){
	if (l<=s&&e<=r){
		f(s,e,o,x);
		return;
	}
	push_down(s,e,o);
	int mid=(s+e)>>1;
	if (mid>=l)update(l,r,x,s,mid,ls(o));
	if (mid+1<=r)update(l,r,x,mid+1,e,rs(o));
	push_up(o);
}
int query(int l,int r,int s=1,int e=n,int o=1){
	if (l<=s&&e<=r){
		return t[o];
	}
	push_down(s,e,o);
	int mid=(s+e)>>1,res=0;
	if (mid>=l)res=(res+query(l,r,s,mid,ls(o)))%p;
	if (mid+1<=r)res=(res+query(l,r,mid+1,e,rs(o)))%p;
	return res;
}
void update_range(int u,int v,int x){
	while (tp[u]!=tp[v]){
		if (dep[tp[u]]<dep[tp[v]])swap(u,v);
		update(id[tp[u]],id[u],x);
		u=fa[tp[u]];
	}
	if (dep[u]>dep[v])swap(u,v);
	update(id[u],id[v],x);
}
int query_range(int u,int v){
	int res=0;
	while (tp[u]!=tp[v]){
		if (dep[tp[u]]<dep[tp[v]])swap(u,v);
		res=(res+query(id[tp[u]],id[u]))%p;
		u=fa[tp[u]];
	}
	if (dep[u]>dep[v])swap(u,v);
	res=(res+query(id[u],id[v]))%p;
	return res;
}
void update_subtree(int u,int x){
	update(id[u],id[u]+sz[u]-1,x);
}
int query_subtree(int u){
	return query(id[u],id[u]+sz[u]-1);
}
void dfs1(int u,int f){
	int t=-1;
	fa[u]=f;
	dep[u]=dep[f]+1;
	sz[u]=1;
	for (const auto &v:g[u]){
		if (v!=f){
			dfs1(v,u);
			sz[u]+=sz[v];
			if (sz[v]>t){
				t=sz[v];
				hs[u]=v;
			}
		}
	}
}
void dfs2(int u,int top){
	tp[u]=top;
	id[u]=++cnt;
	nw[cnt]=w[u];
	if (hs[u]==0)return;
	dfs2(hs[u],top);
	for (const auto &v:g[u]){
		if (v!=hs[u]&&v!=fa[u]){
			dfs2(v,v);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m>>r_id>>p;
	for (int i=1;i<=n;i++)cin>>w[i],w[i]%=p;
	for (int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(r_id,0);
	dfs2(r_id,r_id);
	build();
	for (int i=1;i<=m;i++){
		int op,x,y,z;
		cin>>op;
		if (op==1){
			cin>>x>>y>>z;
			update_range(x,y,z);
		}else if (op==2){
			cin>>x>>y;
			cout<<query_range(x,y)<<"\n";
		}else if (op==3){
			cin>>x>>z;
			update_subtree(x,z);
		}else if (op==4){
			cin>>x;
			cout<<query_subtree(x)<<"\n";
		}
	}
	return 0;
}