P3384 【模板】重链剖分/树链剖分

只贴模版
146行真是要了我的老命！

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;

int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

int n,m,rt,p,head[N],tot,w[N];
int fa[N],dep[N],sz[N],son[N],top[N],dfn[N],idx,nw[N];
struct node{
	int to,nxt;
}edge[N*2];
void add(int x,int y){
	edge[++tot].to=y;
	edge[tot].nxt=head[x];
	head[x]=tot;
}

void dfs1(int x,int father){
	sz[x]=1,fa[x]=father,dep[x]=dep[father]+1;
	for(int i=head[x];i;i=edge[i].nxt){
		int y=edge[i].to;
		if(y==father) continue;
		dfs1(y,x);
		sz[x]+=sz[y];
		if(sz[son[x]]<sz[y]) son[x]=y;
	}
}

void dfs2(int x,int t){
	top[x]=t,dfn[x]=++idx,nw[idx]=w[x];
	if(!son[x]) return;
	dfs2(son[x],t);
	for(int i=head[x];i;i=edge[i].nxt){
		int y=edge[i].to;
		if(y==fa[x]||y==son[x]) continue;
		dfs2(y,y);
	}
}

struct Node{
	int l,r;
	int sum,add;
}tr[N*4];

void pushup(int u){
	tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}

void pushdown(int u){
	Node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
	if(!root.add) return;
	left.add+=root.add,right.add+=root.add;
	left.sum+=(left.r-left.l+1)*root.add,right.sum+=(right.r-right.l+1)*root.add;
	left.sum%=p,right.sum%=p,left.add%=p,right.add%=p,root.add=0;
}

void build(int u,int l,int r){
	if(l==r) tr[u]={l,r,nw[l],0};
	else{
		tr[u].l=l,tr[u].r=r;
		int mid=(l+r)>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
}

void modify(int u,int l,int r,int v){
	if(tr[u].l>=l&&tr[u].r<=r){
		tr[u].add+=v;
		tr[u].sum+=(tr[u].r-tr[u].l+1)*v;
		tr[u].add%=p,tr[u].sum%=p;
	}
	else{
		pushdown(u);
		int mid=(tr[u].l+tr[u].r)>>1;
		if(l<=mid) modify(u<<1,l,r,v);
		if(r>mid) modify(u<<1|1,l,r,v);
		pushup(u); 
	}
}

int query(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1,ans=0;
	if(l<=mid) ans+=query(u<<1,l,r),ans%=p;
	if(r>mid) ans+=query(u<<1|1,l,r),ans%=p;
	return ans%p;
}

int query_sum(int x,int y){
	int fx=top[x],fy=top[y],res=0;
	while(fx!=fy){
		if(dep[fx]>=dep[fy]) res+=query(1,dfn[fx],dfn[x]),x=fa[fx];
		else res+=query(1,dfn[fy],dfn[y]),y=fa[fy];
		fx=top[x],fy=top[y],res%=p;
	}
	if(dfn[x]<dfn[y]) res+=query(1,dfn[x],dfn[y]);
	else res+=query(1,dfn[y],dfn[x]);
	return res%p;
}

void tree_modify(int x,int y,int v){
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(dep[fx]>=dep[fy]) modify(1,dfn[fx],dfn[x],v),x=fa[fx];
		else modify(1,dfn[fy],dfn[y],v),y=fa[fy];
		fx=top[x],fy=top[y];
	}
	if(dfn[x]<dfn[y]) modify(1,dfn[x],dfn[y],v);
	else modify(1,dfn[y],dfn[x],v);
}

int query_subtree(int x){
	return query(1,dfn[x],dfn[x]+sz[x]-1)%p;
}

void subtree_modify(int x,int v){
	modify(1,dfn[x],dfn[x]+sz[x]-1,v);
}

signed main(){
	
	n=read(),m=read(),rt=read(),p=read();
	for(int i=1;i<=n;i++) w[i]=read();
	for(int i=1;i<n;i++){int x=read(),y=read();add(x,y),add(y,x);}
	dfs1(rt,0),dfs2(rt,rt),build(1,1,n);
	while(m--){
		int opt=read(),x,y,z;
		if(opt==1) x=read(),y=read(),z=read(),tree_modify(x,y,z);
		else if(opt==2) x=read(),y=read(),cout<<query_sum(x,y)<<endl;
		else if(opt==3) x=read(),z=read(),subtree_modify(x,z);
		else x=read(),cout<<query_subtree(x)<<endl;
	}
	
	return 0;
}