30 $pts$ : 评测记录

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
const int N=1e5+10,M=1e5+10;
struct segment_tree{
	int sum,lazy;
}tree[N<<2];
struct chain_forward_star{
	int nxt,to;
}edge[M<<1];
int head[N],size[N],top[N],fa[N],son[N],a[N],w[N],dep[N],id[N],n,start,q,mod,cnt,e_cnt;
inline void add(int x,int y){
	edge[++e_cnt]=(chain_forward_star){head[x],y},head[x]=e_cnt;
}
void dfs1(int x,int pre){
	size[x]=1;
	for(int i=head[x];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v!=pre){
			dep[v]=dep[x]+1,fa[v]=x;
			dfs1(v,x);
			size[x]+=size[v];
			if(size[v]>size[son[x]]) son[x]=v;
		}
	}
}
void dfs2(int x,int sum){
	id[x]=++cnt,a[cnt]=w[x],top[x]=sum;
	if(son[x]) dfs2(son[x],sum);
	for(int i=head[x];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v!=fa[x]&&v!=son[x]) dfs2(v,v);
	}
}
inline void pushup(int x){
	tree[x].sum=(tree[ls(x)].sum+tree[rs(x)].sum)%mod;
}
inline void pushdown(int x,int l,int r){
	int mid=(l+r)>>1;
	tree[ls(x)].lazy=(tree[ls(x)].lazy+tree[x].lazy)%mod,tree[rs(x)].lazy=(tree[rs(x)].lazy+tree[x].lazy)%mod;
	tree[ls(x)].sum=((mid-l+1)*tree[x].lazy+tree[ls(x)].sum)%mod,tree[rs(x)].sum=((r-mid)*tree[x].lazy+tree[rs(x)].sum)%mod;
	tree[x].lazy=0;
}
void build(int x,int l,int r){
	tree[x].sum=tree[x].lazy=0;
	if(l==r) return (void)(tree[x].sum=a[l]%mod);
	int mid=(l+r)>>1;
	build(ls(x),l,mid),build(rs(x),mid+1,r);
	pushup(x);
}
void update(int x,int l,int r,int L,int R,int sum){
	if(R<l||L>r) return;
	if(L<=l&&r<=R) return (void)(tree[x].sum+=(r-l+1)*sum%mod,tree[x].lazy+=sum%mod);
	if(tree[x].lazy) pushdown(x,l,r);
	int mid=(l+r)>>1;
	if(L<=mid) update(ls(x),l,mid,L,R,sum);
	if(R>mid) update(rs(x),mid+1,r,L,R,sum);
	pushup(x);
}
ll query(int x,int l,int r,int L,int R){
	if(R<l||L>r) return 0;
	if(L<=l&&r<=R) return tree[x].sum;
	if(tree[x].lazy) pushdown(x,l,r);
	int mid=(l+r)>>1;
	return (L<=mid?query(ls(x),l,mid,L,R):0)+(R>mid?query(rs(x),mid+1,r,L,R):0);
}
void update_chain(int x,int y,int sum){
	int fax=top[x],fay=top[y];
	while(fax!=fay){
		if(dep[fax]<dep[fay]) swap(x,y),swap(fax,fay);
		update(1,1,cnt,id[fax],id[x],sum),x=fa[fax],fax=top[x];
	}
	if(id[x]>id[y]) swap(x,y);
	update(1,1,cnt,id[x],id[y],sum);
}
int query_chain(int x,int y){
	int ans=0,fax=top[x],fay=top[y];
	while(fax!=fay){
		if(dep[fax]<dep[fay]) swap(x,y),swap(fax,fay);
		ans+=query(1,1,cnt,id[fax],id[x]),x=fa[fax],fax=top[x];
	}
	if(id[x]>id[y]) swap(x,y);
	return ans+query(1,1,cnt,id[x],id[y]);
}
int main(){
	scanf("%d%d%d%d",&n,&q,&start,&mod);
	for(int i=1;i<=n;i++) scanf("%d",&w[i]);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs1(start,-1),dfs2(start,start),build(1,1,n);
	while(q--){
		int l,r,sum;
		char opt;
		scanf(" %c%d",&opt,&l);
		if(opt=='1'){
			scanf("%d%d",&r,&sum);
			update_chain(l,r,sum%mod);
		}
		else if(opt=='2'){
			scanf("%d",&r);
			printf("%d\n",query_chain(l,r));
		}
		else if(opt=='3'){
			scanf("%d",&sum);
			update(1,1,n,id[l],id[l]+size[l]-1,sum);
		}
		else printf("%d\n",query(1,1,n,id[l],id[l]+size[l]-1));
	}
	return 0;
}

如果有哪位好心肯帮帮忙，在此道谢！