留坑待补，先放代码
#include<iostream> #include<cstdio> #include<cstring> #include<bitset> #include<queue> #include<algorithm> #define int long long #define rii register int i #define rij register int j using namespace std; int n,m,r,p; struct ljb{ int to,nxt; }x[400005]; struct node{ int val,lazy; }y[600005]; int f[200005],sd[200005],head[200005],val[200005],size[200005]; int weison[200005],cnt,bnt,nid[200005],nval[200005],ntop[200005]; int res; void add(int from,int to) { cnt++; x[cnt].to=to; x[cnt].nxt=head[from]; head[from]=cnt; } void dfs1(int wz,int fa,int s) { sd[wz]=s; f[wz]=fa; size[wz]=1; int maxn=0; for(rii=head[wz];i!=0;i=x[i].nxt) { int to=x[i].to; if(to==fa) { continue; } dfs1(to,wz,s+1); size[wz]+=size[to]; if(size[to]>maxn) { maxn=size[to]; weison[wz]=to; } } } void dfs2(int wz,int top) { bnt++; nid[wz]=bnt; nval[bnt]=val[wz]; ntop[wz]=top; if(weison[wz]==0) { return; } dfs2(weison[wz],top); for(rii=head[wz];i!=0;i=x[i].nxt) { int to=x[i].to; if(weison[wz]==to||f[wz]==to) { continue; } dfs2(to,to); } } void build(int bh,int l,int r) { if(l==r) { y[bh].val=nval[l]; y[bh].val%=p; return; } int mid=(l+r)/2; build(bh*2,l,mid); build(bh*2+1,mid+1,r); y[bh].val+=y[bh*2].val+y[bh*2+1].val; y[bh].val%=p; } void pushdown(int bh,int cd) { y[bh*2].lazy+=y[bh].lazy; y[bh*2+1].lazy+=y[bh].lazy; y[bh*2].val+=y[bh].lazy*(cd-(cd/2)); y[bh*2+1].val+=y[bh].lazy*(cd/2); y[bh*2].val%=p; y[bh*2+1].val%=p; y[bh].lazy=0; } void updata(int bh,int nl,int nr,int l,int r,int val) { int len=(nr-nl+1); if(l<=nl&&nr<=r) { y[bh].lazy+=val; y[bh].val+=val*len; y[bh].val%=p; return; } if(y[bh].lazy!=0) { pushdown(bh,len); } int mid=(nl+nr)/2; if(l<=mid) { updata(bh*2,nl,mid,l,r,val); } if(r>mid) { updata(bh*2+1,mid+1,nr,l,r,val); } y[bh].val=(y[bh*2].val+y[bh*2+1].val)%p; } void query(int bh,int nl,int nr,int l,int r) { if(l<=nl&&r>=nr) { res+=y[bh].val; res%=p; return; } int mid=(nl+nr)/2; if(y[bh].lazy!=0) { pushdown(bh,nr-nl+1); } if(l<=mid) { query(bh*2,nl,mid,l,r); } if(r>mid) { query(bh*2+1,mid+1,nr,l,r); } } int querylj(int from,int to) { int ans=0; while(ntop[from]!=ntop[to]) { if(sd[ntop[from]]<sd[ntop[to]]) { swap(from,to); } res=0; query(1,1,n,nid[ntop[from]],nid[from]); ans+=res; ans%=p; from=f[ntop[from]]; } if(sd[from]>sd[to]) { swap(from,to); } res=0; query(1,1,n,nid[from],nid[to]); ans+=res; ans%=p; return ans; } void addlj(int from,int to,int val) { val%=p; while(ntop[from]!=ntop[to]) { if(sd[ntop[from]]<sd[ntop[to]]) { swap(from,to); } updata(1,1,n,nid[ntop[from]],nid[from],val); from=f[ntop[from]]; } if(sd[from]>sd[to]) { swap(from,to); } updata(1,1,n,nid[from],nid[to],val); } void addson(int wz,int val) { updata(1,1,n,nid[wz],nid[wz]+size[wz]-1,val); } int queryson(int wz) { res=0; query(1,1,n,nid[wz],nid[wz]+size[wz]-1); return res; } signed main() { scanf("%lld%lld%lld%lld",&n,&m,&r,&p); for(rii=1;i<=n;i++) { scanf("%lld",&val[i]); } for(rii=1;i<n;i++) { int from,to; scanf("%lld%lld",&from,&to); add(from,to); add(to,from); } dfs1(r,0,2); dfs2(r,r); build(1,1,n); for(rii=1;i<=m;i++) { int opt,from,to,val,kkk; scanf("%lld",&opt); if(opt==1) { scanf("%lld%lld",&from,&to); scanf("%lld",&val); addlj(from,to,val); } if(opt==2) { scanf("%lld%lld",&from,&to); kkk=querylj(from,to); printf("%lld ",kkk); } if(opt==3) { scanf("%lld%lld",&from,&val); addson(from,val); } if(opt==4) { scanf("%lld",&from); kkk=queryson(from); printf("%lld ",kkk); } } }