树状数组30分求助，码量不大qwq(悬赏关注

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;
const int maxN=1e5+100;
int n,m,root,p,idx;
int val[maxN],size[maxN],top[maxN],fa[maxN],dep[maxN];
int mson[maxN],dfn[maxN],amap[maxN],vis[maxN],tv[maxN];
//树链剖分部分
int deal[maxN],dealx[maxN];//存原来的差分数组，dealx[i]=deal[i]*(i-1) 
//EX-BIT部分 
vector<int> g[maxN];

int lowbit(int x){
	return x&-x;
}
void add(int l,int r,int x){
	for(int i=l;i<=maxN;i+=lowbit(i))
		deal[i]+=x,dealx[i]+=(l-1)*x;
	for(int i=r+1;i<=maxN;i+=lowbit(i))
		deal[i]-=x,dealx[i]-=r*x;
}

int sum(int l,int r){
	int s1=0,s2=0;
	for(int i=l-1;i>0;i-=lowbit(i))
		s1+=deal[i]*(l-1)-dealx[i];
	for(int i=r;i>0;i-=lowbit(i))
		s2+=deal[i]*r-dealx[i];
	return (s2-s1);
}

void build(){
	for(int i=1;i<=n;i++)
		add(i,i,val[amap[i]]);
}

void dfs1(int now,int f){
	fa[now]=f,size[now]=1,dep[now]=dep[f]+1;
	int maxs=0;
	for(int x:g[now]){
		if(vis[x]) continue ;
		vis[x]=1,dfs1(x,now);
		size[now]+=size[x];
		if(maxs<size[x])
			maxs=size[x],mson[now]=x;
	}
}

void dfs2(int now,int tp){
	top[now]=tp,dfn[now]=++idx,amap[idx]=now;
	if(mson[now]) vis[mson[now]]=1,dfs2(mson[now],tp);
	for(int x:g[now]){
		if(vis[x]) continue ;
		vis[x]=1;
		dfs2(x,x);
	}
}

int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) y=fa[top[y]];
		else x=fa[top[x]];
	}
	return (dep[x]<dep[y])?x:y;
}



void add_chain(int x,int y,int z){//dep[x]>dep[y] 
	while(top[x]!=top[y]){
		add(dfn[top[x]],dfn[x],z);
		x=fa[top[x]];
	}
	add(dfn[y],dfn[x],z);
}

void add_path(int x,int y,int c){
	int z=lca(x,y);
	if(x==z) add_chain(y,z,c);//cout<<1 << endl;
	else if(y==z) add_chain(x,z,c);//cout << 2 << endl;
	else add_chain(x,z,c),add_chain(y,z,c),add(dfn[z],dfn[z],-c);//lca处加了两遍 
}

int sum_chain(int x,int y){
	int s=0;
	while(top[x]!=top[y]){
		s=(sum(dfn[top[x]],dfn[x])+s)%p;
		x=fa[top[x]];
	}
	return (s+sum(dfn[y],dfn[x]))%p;
}

int sum_path(int x,int y){
	int z=lca(x,y);
	if(x==z) return sum_chain(y,z);
	else if(y==z) return sum_chain(x,z);
	else return (sum_chain(x,z)+sum_chain(y,z)-sum(dfn[z],dfn[z]))%p;
}

int add_son(int x,int z){
	add(dfn[x],dfn[x]+size[x]-1,z);
}

int sum_son(int x){
	return sum(dfn[x],dfn[x]+size[x]-1);
}

void listdata(){
	cout << endl;
	for(int i=1;i<=n;i++){
		cout << mson[i] << " " << size[i] << " " << dfn[i]  << " " << amap[i]<< endl;
	}
	cout << endl;
}

int main(){
	ios::sync_with_stdio(false);//cin加速 
	cin >> n >> m >> root >> p;
	for(int i=1;i<=n;i++) cin >> val[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);  
	}
	vis[root]=1;
	dfs1(root,root);
	memset(vis,0,sizeof(vis));
	vis[root]=1;//listdata();
	dfs2(root,root);
	//cout <<1<< endl;
	build(); 
	

	
	while(m--){
		int s,x,y,z;
		cin >> s;
		switch (s){
			case 1:
				cin >> x >> y >> z;
				add_path(x,y,z);
				break;
			case 2:
				cin >> x >> y;
				cout << sum_path(x,y) << endl;
				break;
			case 3:	
				cin >> x >> z ;
				add_son(x,z);
				break;
			case 4:
				cin >> x;
				cout << sum_son(x) << endl;
				break;	
		} 
	}
	
	return 114514-114514;
}