70行树剖板子了解一下

#include<cstdio>
#include<algorithm>
#define gt getchar()
#define ls l,mid,k<<1
#define rs mid+1,r,k<<1|1
#define ps sum[k]=MO(sum[k<<1]+sum[k<<1|1])
inline int in(){int k;scanf("%d",&k);return k;}
const int N=1e5+5;int YL;
inline int MO(const int &a){return a>=YL?a-YL:a;}
inline void add(int &x,int y){x+=y;if(x>=YL)x-=YL;}
int head[N],to[N<<1],nxt[N<<1],cnt,val[N],son[N],top[N],siz[N],fa[N],dep[N],n,id[N],pos[N],sum[N<<2],lz[N<<2];
inline void link(int u,int v){to[++cnt]=v,nxt[cnt]=head[u],head[u]=cnt;to[++cnt]=u,nxt[cnt]=head[v],head[v]=cnt;}
void dfs(int u,int pa=0)
{
	siz[u]=1,fa[u]=pa;dep[u]=dep[pa]+1;
	for(int i=head[u],v;i;i=nxt[i])
		if((v=to[i])!=pa)dfs(v,u),son[u]=(siz[son[u]]<siz[v]?v:son[u]),siz[u]+=siz[v];
}
void build(int l,int r,int k)
{
	if(l==r){sum[k]=val[pos[l]];return;}
	int mid=l+r>>1;build(ls),build(rs);ps;
}
void pushdown(int k,int l,int r)
{
	if(!lz[k])return;int le=1ll*l*lz[k]%YL,ri=1ll*r*lz[k]%YL;
	add(lz[k<<1],lz[k]),add(lz[k<<1|1],lz[k]),add(sum[k<<1],le),add(sum[k<<1|1],ri);lz[k]=0;
}
void update(int L,int R,int l,int r,int k,int ad)
{
	if(L<=l&&r<=R){int t=1ll*ad*(r-l+1)%YL;add(sum[k],t);add(lz[k],ad);return;}
	int mid=l+r>>1;pushdown(k,mid-l+1,r-mid);if(L<=mid)update(L,R,ls,ad);if(R> mid)update(L,R,rs,ad);ps;
}
int query(int L,int R,int l,int r,int k)
{
	if(L<=l&&r<=R)return sum[k];int mid=l+r>>1,ans=0;pushdown(k,mid-l+1,r-mid);
	if(L<=mid)add(ans,query(L,R,ls));if(R> mid)add(ans,query(L,R,rs));return ps,ans;
}
#define pd if(dep[top[u]]<dep[top[v]])std::swap(u,v)
void Dfs(int u,int tp)
{
	top[u]=tp,id[u]=++cnt,pos[cnt]=u;if(son[u])Dfs(son[u],tp);
	for(int i=head[u],v;i;i=nxt[i])if((v=to[i])!=fa[u]&&v!=son[u])Dfs(v,v);
}
void change(int u,int v,int ad)
{
	while(top[u]!=top[v]){pd;update(id[top[u]],id[u],1,n,1,ad);u=fa[top[u]];}
	if(dep[u]>dep[v])std::swap(u,v);update(id[u],id[v],1,n,1,ad);
}
int ask(int u,int v,int ans=0)
{
	while(top[u]!=top[v]){pd;add(ans,query(id[top[u]],id[u],1,n,1));u=fa[top[u]];}
	if(dep[u]>dep[v])std::swap(u,v);add(ans,query(id[u],id[v],1,n,1));return ans;
}
int main()
{
	n=in();int m=in(),s=in(),op,x,y,z;YL=in();
	for(int i=1;i<=n;++i)val[i]=in();
	for(int i=2;i<=n;++i)link(in(),in());cnt=0;
	dfs(s);Dfs(s,s);build(1,n,1);
	for(int i=1;i<=m&&(op=in(),x=in(),1);++i)
		switch(op)
		{
		case 1:y=in(),z=in()%YL,change(x,y,z);break;
		case 2:y=in(),printf("%d\n",ask(x,y));break;
		case 3:z=in()%YL,update(id[x],id[x]+siz[x]-1,1,n,1,z);break;
		case 4:printf("%d\n",query(id[x],id[x]+siz[x]-1,1,n,1));break;
		}
	return 0;
}