rt,听说灌水区人多

原题模板

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+7;
int N,M,R,P,w[maxn],dep[maxn];
int head[maxn],nxt[maxn],to[maxn],cnt;//邻接表全家桶 
int Fa[maxn],Hd[maxn],Hson[maxn],SZ[maxn],id[maxn];
//树剖全家桶(爹,i的重链头,重儿子,子树大小,在线段树的位置 )
struct node{int l,r,dat,add;}tree[maxn];
void edge(int U,int V){
	nxt[++cnt]=head[U];to[cnt]=V;head[U]=cnt;
	nxt[++cnt]=head[V];to[cnt]=U;head[V]=cnt;
	return;
}
//以下为线段树 
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
int Mid(int l,int r){return (l+r)>>1;}
void build(int l,int r,int p){//建树 
	tree[p].l=l;tree[p].r=r;
	if(l==r){tree[p].dat=w[l];return;}
	int mid=Mid(l,r);
	build(l,mid,ls(p));build(mid+1,r,rs(p));
	tree[p].dat=tree[ls(p)].dat+tree[rs(p)].dat;
	return;
}
void lazy(int p){//懒标记
	if(tree[p].add){
		tree[ls(p)].dat+=tree[p].add*(tree[ls(p)].r-tree[ls(p)].l+1);
		tree[rs(p)].dat+=tree[p].add*(tree[rs(p)].r-tree[rs(p)].l+1);
		tree[ls(p)].add+=tree[p].add;tree[rs(p)].add+=tree[p].add;
		tree[p].add=0; 
	}
	return; 
}
void change(int p,int l,int r,int k){
	//cout<<"changeing L:"<<l<<" R: "<<r<<endl; 
	//cout<<"现在事节点 "<<p<<"从 "<<tree[p].l<<" 到 "<<tree[p].r<<endl;
	if(l<=tree[p].l&&r>=tree[p].r){
		tree[p].dat+=1LL*k*(tree[p].r-tree[p].l+1);
		tree[p].add+=k;
		return;
	}
	int mid=Mid(tree[p].l,tree[p].r);
	if(l<=mid)change(ls(p),l,r,k);
	if(r>mid)change(rs(p),l,r,k);
	tree[p].dat=tree[ls(p)].dat+tree[rs(p)].dat;
	return;
}
long long ask(int p,int l,int r){
	if(l<=tree[p].l&&r>=tree[p].r)return tree[p].dat;
	lazy(p);
	int mid=Mid(tree[p].l,tree[p].r);
	long long ret=0;
	if(l<=mid)ret+=ask(ls(p),l,r);
	if(r>mid)ret+=ask(rs(p),l,r);
	return ret;
}
//线段树部分结束 
//它 来 了
int dfs1(int u,int fa){
	SZ[u]=1;Fa[u]=fa;dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v!=fa){
			SZ[u]+=dfs1(v,u);
			if(SZ[v]>SZ[Hson[u]])Hson[u]=v;
		}
	}
	return SZ[u]; 
}
void dfs2(int u,int fa,int _H){//当前节点,爹,重链头 
	id[u]=++cnt;Hd[u]=_H;
	if(Hson[u])dfs2(Hson[u],u,_H);
	for(int i=head[u];i;i=nxt[i])
		if(to[i]!=fa&&to[i]!=Hson[u])dfs2(to[i],u,to[i]);
	return;
}
void add(int u,int v,int w){
	while(1){
		int hu=Hd[u],hv=Hd[v];
		if(hu==hv)break;
		if(dep[hu]<dep[hv])swap(u,v),swap(hu,hv);
		change(1,id[hu],id[u],w);u=Fa[hu];
	}
	if(dep[u]<dep[v])swap(u,v);
	change(1,id[v],id[u],w);
	return;
}
//E · N · D 
int main(){
	scanf("%d%d%d%d",&N,&M,&R,&P);
	for(int i=1;i<=N;i++)scanf("%d",&w[i]);
	for(int i=1;i<N;i++){int a,b;scanf("%d%d",&a,&b);edge(a,b);}
	cnt=0;//!!!!!!!
	dfs1(R,0);
	dfs2(R,0,R); 
	build(1,N,1);
	while(M--){
		int op,x,y,z;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
		}else if(op==2){
			scanf("%d%d",&x,&y);
			if(id[x]>id[y])swap(x,y);
			printf("%d\n",ask(1,id[x],id[y])%P);
		}else if(op==3){
			scanf("%d%d",&x,&y);
			change(1,id[x],id[x]+SZ[x]-1,y);
		}else{
			scanf("%d",&x);
			printf("%d\n",ask(1,id[x],id[x]+SZ[x]-1)%P);
		}
	}
	return 0;
}