WxjzKK @ 2023-11-17 20:54:51
要考 $NOIP$ 了,急,玄关。
开了 `long long` 并没有什么卵用。
```cpp
//【模板】树链剖分
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
inline void read(int &n){
int s=0,t=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') t=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<3)+(s<<1)+(c^48);c=getchar();
}
n=s*t;
}
inline void put(int n){
if(n<0){
putchar('-');n=-n;
}
if(n<10){
putchar(n+48);return;
}
put(n/10);
putchar(n%10+48);
}
struct node{
int v,nxt;
}e[MAXN<<1];
struct sgt{
int l,r,sum,tag;
}t[MAXN<<1];
int n,p,root,tot,cnt,tal,a[MAXN],b[MAXN],head[MAXN],dep[MAXN],siz[MAXN],fa[MAXN],son[MAXN],id[MAXN],top[MAXN];
inline void add(int u,int v){
++tot;
e[tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
}
inline void dfs1(int u,int f){
fa[u]=f;dep[u]=dep[f]+1;siz[u]=1;
for(register int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=f){
dfs1(v,u);siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
}
inline void dfs2(int u,int ltop){
id[u]=++cnt;b[cnt]=a[u];top[u]=ltop;
if(son[u]) dfs2(son[u],ltop);
for(register int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
}
inline void pushup(int rt){
t[rt].sum=(t[t[rt].l].sum+t[t[rt].r].sum)%p;
}
inline void pushdown(int rt,int l,int r){
if(t[rt].tag){
int mid=(l+r)>>1;
t[t[rt].l].sum=(t[t[rt].l].sum+(mid-l+1)*t[rt].tag)%p;
t[t[rt].r].sum=(t[t[rt].r].sum+(r-mid)*t[rt].tag)%p;
t[t[rt].l].tag=(t[t[rt].l].tag+t[rt].tag)%p;
t[t[rt].r].tag=(t[t[rt].r].tag+t[rt].tag)%p;
t[rt].tag=0;
}
}
inline void build(int &rt,int l,int r){
if(!rt) rt=++tot;
if(l==r){
t[tot].sum=b[l]%p;return;
}
int mid=(l+r)>>1;
build(t[rt].l,l,mid);build(t[rt].r,mid+1,r);
pushup(rt);
}
inline void update(int rt,int l,int r,int left,int right,int x){
if(l>=left&&r<=right){
t[rt].sum=(t[rt].sum+(r-l+1)*x)%p;t[rt].tag=(t[rt].tag+x)%p;return;
}
pushdown(rt,l,r);
int mid=(l+r)>>1;
if(left<=mid) update(t[rt].l,l,mid,left,right,x);
if(right>mid) update(t[rt].r,mid+1,r,left,right,x);
pushup(rt);
}
inline int query(int rt,int l,int r,int left,int right){
if(l>=left&&r<=right) return t[rt].sum;
pushdown(rt,l,r);
int mid=(l+r)>>1,ans=0;
if(left<=mid) ans=(ans+query(t[rt].l,l,mid,left,right))%p;
if(right>mid) ans=(ans+query(t[rt].r,mid+1,r,left,right))%p;
return ans;
}
inline void range(int x,int y,int z){
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]) swap(x,y);
update(root,1,n,id[top[y]],id[y],z);y=fa[top[y]];
}
if(dep[x]>dep[y]) swap(x,y);
update(root,1,n,id[x],id[y],z);
}
inline int getsum(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]) swap(x,y);
ans=(ans+query(root,1,n,id[top[y]],id[y]))%p;y=fa[top[y]];
}
if(dep[x]>dep[y]) swap(x,y);
ans=(ans+query(root,1,n,id[x],id[y]))%p;
return ans;
}
int main(){
int m,r,opt,x,y,z;
read(n);read(m);read(r);read(p);
for(register int i=1;i<=n;++i) read(a[i]);
for(register int i=1;i<n;++i){
read(x);read(y);add(x,y);add(y,x);
}
dfs1(r,0);dfs2(r,r);build(root,1,n);
for(register int i=1;i<=m;++i){
read(opt);read(x);
if(opt==1){
read(y);read(z);range(x,y,z%p);
}
else if(opt==2){
read(y);put(getsum(x,y));putchar('\n');
}
else if(opt==3){
read(z);update(root,1,n,id[x],id[x]+siz[x]-1,z%p);
}
else{
put(query(root,1,n,id[x],id[x]+siz[x]-1));putchar('\n');
}
}
return 0;
}
```