P3384,救一下孩子把,取模炸了没调出来题目
#include<bits/stdc++.h>
#define int long long
const int N=114514;
using namespace std;
int head[N],cnt;
int dfn;
int n,m,rt,mod,a[N],w[N],tree[N*4],lazy[N];
int ls(int p){return p<<1;}
int rs(int p){return (p<<1)+1;}
struct edge{
int next,to;
}e[N];
void add_edge(int u,int v){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
struct node{
int size,top,son,dep,fa,id,rk;
node(){
memset(this,0,sizeof(node));
}
}p[N];
void dfs(int u,int fa){
p[u].fa=fa;//结点的父亲
p[u].size=1;//子树的结点个数
p[u].dep=p[fa].dep+1;//结点深度
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
p[u].size+=p[v].size;
if(p[u].son==0|p[v].size>p[p[u].son].size){
p[u].son=v;//重儿子
}
}
}
void dfs2(int u,int t){
p[u].id=++dfn;
p[u].top=t;
if(!p[u].son) return;
dfs2(p[u].son,t);//先遍历重儿子
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v==p[u].fa|v==p[u].son) continue;
dfs2(v,v);
}
}
void pushup(int p){
tree[p]=(tree[ls(p)]+tree[rs(p)])%mod;
}
void build(int p,int pl,int pr){
if(pl==pr){tree[p]=w[pl];return;}
int mid=(pl+pr)>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
pushup(p);
}
void add(int p,int pl,int pr,int k){
lazy[p]=(lazy[p]+k);
tree[p]=(tree[p]+(pr-pl+1)*k);
}
void pushdown(int p,int pl,int pr){
if(lazy[p]){
int mid=(pl+pr)>>1;
add(ls(p),pl,mid,lazy[p]);
add(rs(p),mid+1,pr,lazy[p]);
lazy[p]=0;
}
}
void update(int p,int pl,int pr,int l,int r,int k){
if(l<=pl&&pr<=r){
add(p,pl,pr,k);
return;
}
pushdown(p,pl,pr);
int mid=(pl+pr)>>1;
if(l<=mid) update(ls(p),pl,mid,l,r,k);
if(mid<r) update(rs(p),mid+1,pr,l,r,k);
pushup(p);
}
int query(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r){return tree[p]%mod;}
int res=0,mid=(pl+pr)>>1;
pushdown(p,pl,pr);
if(l<=mid) res=(res+query(ls(p),pl,mid,l,r))%mod;
if(mid<r) res=(res+query(rs(p),mid+1,pr,l,r))%mod;
return res%mod;
}
void upd_c(int x,int y,int k){
while(p[x].top!=p[y].top){//不在同一个链上
if(p[p[x].top].dep<p[p[y].top].dep){swap(x,y);}//让链顶深度深
update(1,1,n,p[p[x].top].id,p[x].id,k);
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep){swap(x,y);}
update(1,1,n,p[y].id,p[x].id,k);
}
int que_c(int x,int y){
int res=0;
while(p[x].top!=p[y].top){
if(p[p[x].top].dep<p[p[y].top].dep){swap(x,y);}
res=(res+query(1,1,n,p[p[x].top].id,p[x].id))%mod;
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep) {swap(x,y);}
res=(res+query(1,1,n,p[y].id,p[x].id))%mod;
return res%mod;
}
void upd_r(int x,int k){
update(1,1,n,p[x].id,p[x].id+p[x].size-1,k);
}
int que_r(int x){
return query(1,1,n,p[x].id,p[x].id+p[x].size-1)%mod;
}
signed main(){
cin>>n>>m>>rt>>mod;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n-1;i++){
int x,y;
cin>>x>>y;
add_edge(x,y);
add_edge(y,x);
}
dfs(rt,rt);
dfs2(rt,rt);
for(int i=1;i<=n;i++){
w[p[i].id]=a[i];
}
build(1,1,n);
while(m--){
int op,x,y,z;
cin>>op;
if(op==1){
cin>>x>>y>>z;
upd_c(x,y,z);
}
else if(op==2){
cin>>x>>y;
cout<<que_c(x,y)<<endl;
}
else if(op==3){
cin>>x>>z;
upd_r(x,z);
}
else{
cin>>x;
cout<<que_r(x)<<endl;
}
}
//system("pause");
return 0;
}