UQAQU @ 2024-08-01 22:40:34
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const ll N=5000007;
ll n,m,r,mod;
struct tree{
ll next,to,w;
}edge[2*N];
ll head[N],top[N],father[N],son[N],cnt;
ll val[N],num[N],id[N],size[N],deep[N],number;
ll d[4*N],lazy[N*4];
inline ll read(){
ll ans=0,res=1;
char c;
while (c<'0' || c>'9'){
if (c=='-'){
res=-1;
}
c=getchar();
}
while (c>='0' && c<='9'){
ans=(ans<<3)+(ans<<1)+(c^48);
c=getchar();
}
return ans*res;
}
void add_edge(ll u,ll v){
cnt++,edge[cnt].to=v,edge[cnt].next=head[u],head[u]=cnt;
}
void dfs1(ll u,ll v){
deep[u]=deep[v]+1;
father[u]=v;
size[u]=1;
for (ll i=head[u];i!=0;i=edge[i].next){
ll j=edge[i].to;
if (j==v){
continue;
}
dfs1(j,u);
size[u]+=size[j];
if (size[j]>size[son[u]]){
son[u]=j;
}
}
}
void dfs2(ll u,ll tp){
number++;
id[u]=number;
val[number]=u;
top[u]=tp;
if (!son[u]){
return ;
}
dfs2(son[u],tp);
for (ll i=head[u];i!=0;i=edge[i].next){
ll j=edge[i].to;
if (j==son[u] || j==father[u]){
continue;
}
dfs2(j,j);
}
}
void build(ll l,ll r,ll p){
if (l==r){
d[p]=num[val[l]];
return ;
}
ll mid=l+((r-l)>>1);
build(l,mid,2*p),build(mid+1,r,2*p+1);
d[p]+=d[2*p]+d[p*2+1];
d[p]%=mod;
return ;
}
ll query(ll l,ll r,ll s,ll t,ll p){
if (l<=s && t<=r){
return d[p]%mod;
}
if (s>r || t<l){
return 0;
}
ll mid=s+((t-s)>>1);
if (lazy[p]!=0){
d[p*2]+=lazy[p]*(mid-s+1),d[p*2+1]+=lazy[p]*(t-mid);
d[p*2]%=mod,d[p*2+1]%=mod;
lazy[p*2]+=lazy[p],lazy[p*2+1]+=lazy[p],lazy[2*p]%=mod,lazy[2*p+1]%=mod;
lazy[p]=0;
}
ll ans=0;
if (l<=mid){
ans+=query(l,r,s,mid,p*2);
ans%=mod;
}
if (r>mid){
ans+=query(l,r,mid+1,t,2*p+1);
ans%=mod;
}
return ans%=mod;
}
ll query_sum(ll u,ll v){
ll res=0;
while(top[u]!=top[v]){
if (deep[top[u]]<deep[top[v]]){
swap(u,v);
}
res+=query(id[top[u]],id[u],1,number,1);
u=father[top[u]];
res%=mod;
}
if (deep[u]<deep[v]){
swap(u,v);
}
res+=query(id[v],id[u],1,number,1);
res%=mod;
return res%mod;
}
ll query_tree(ll u){
return query(id[u],id[u]+size[u]-1,1,number,1);
}
void update(ll l,ll r,ll s,ll t,ll k,ll p){
if (l<=s && t<=r){
d[p]+=(t-s+1)*k,lazy[p]+=k;
d[p]%=mod;
lazy[p]%=mod;
return ;
}
if (s>r || t<l){
return ;
}
ll mid=s+((t-s)>>1);
if (lazy[p]!=0 && s!=t){
d[2*p]+=lazy[p]*(mid-s+1),d[p*2+1]+=lazy[p]*(t-mid);
d[p*2]%=mod,d[p*2+1]%=mod;
lazy[p*2]+=lazy[p],lazy[p*2+1]+=lazy[p];
lazy[p*2]%=mod,lazy[p*2+1]%=mod;
lazy[p]=0;
}
if (l<=mid){
update(l,r,s,mid,k,2*p);
}
if (r>mid){
update(l,r,mid+1,t,k,2*p+1);
}
d[p]=d[p*2]+d[p*2+1];
d[p]%=mod;
}
void update_path(ll u,ll v,ll k){
while(top[u]!=top[v]){
if (deep[u]<deep[v]){
swap(u,v);
}
update(id[top[u]],id[u],1,number,k,1);
u=father[top[u]];
}
if (deep[u]<deep[v]){
swap(u,v);
}
update(id[v],id[u],1,number,k,1);
}
void update_tree(ll u,ll k){
update(id[u],id[u]+size[u]-1,1,number,k,1);
}
int main()
{
n=read(),m=read(),r=read(),mod=read();
for (ll i=1;i<=n;i++){
num[i]=read();
num[i]%=mod;
}
for (ll i=1;i<=n-1;i++){
ll x,y;
x=read(),y=read();
add_edge(x,y);
add_edge(y,x);
}
dfs1(r,0);
dfs2(r,r);
build(1,n,1);
while (m--){
ll t,x,y,z;
t=read();
if (t==1){
x=read(),y=read(),z=read();
update_path(x,y,z);
}
if (t==2){
x=read(),y=read();
cout<<query_sum(x,y)%mod<<endl;
}
if (t==3){
x=read(),z=read();
update_tree(x,z);
}
if (t==4){
x=read();
cout<<query_tree(x)%mod<<endl;
}
}
return 0;
}#include<bits/stdc++.h>
#define ll long long int
const int N=5e6+7;
using namespace std;
struct tree{
int to,next,w;
}edge[2*N];
int n,m,r,mod;
int head[N],cnt,deep[N],sum[N],ch[N];
int top[N],fa[N],son[N],number,size[N],val[N],lazy[N],id[N];
void add_edge(int u,int v){
cnt++;
edge[cnt].to=v,edge[cnt].next=head[u],head[u]=cnt;
}
void dfs1(int u,int v){
deep[u]=deep[v]+1;
fa[u]=v;
size[u]=1;
for (int i=head[u];i!=0;i=edge[i].next){
int j=edge[i].to;
if (j==v){
continue;
}
dfs1(j,u);
size[u]+=size[j];
if (size[j]>size[son[u]]){
son[u]=j;
}
}
}
void dfs2(int u,int v){
number++;
id[u]=number,val[number]=u,top[u]=v;
if (!son[u]){
return ;
}
dfs2(son[u],v);
for (int i=head[u];i!=0;i=edge[i].next){
int j=edge[i].to;
if (j!=fa[u] && j!=son[u]){
dfs2(j,j);
}
}
return ;
}
void build(int u,int l,int r){
if (l==r){
sum[u]=ch[val[l]];
return ;
}
int mid=(l+r)>>1;
build(2*u,l,mid);
build(2*u+1,mid+1,r);
sum[u]+=sum[2*u]+sum[2*u+1];
sum[u]%=mod;
return ;
}
void push(int u,int l,int r){
int mid=(l+r)>>1;
lazy[2*u]+=lazy[u];lazy[2*u]%=mod;
lazy[2*u+1]+=lazy[u];lazy[2*u+1]%=mod;
sum[2*u]+=lazy[u]*(mid-l+1);sum[2*u]%=mod;
sum[2*u+1]+=lazy[u]*(r-mid);sum[2*u]%=mod;
lazy[u]=0;
return ;
}
void update(int u,int s,int t,int l,int r,int k){
if (l<=s && r>=t){
sum[u]+=k*(t-s+1);sum[u]%=mod;
lazy[u]+=k;lazy[u]%=mod;
return ;
}
if(s>r||t<l)return ;
int mid=(s+t)>>1;
if (lazy[u]!=0){
push(u,s,t);
}
if (l>=mid){
update(2*u,s,mid,l,r,k);
}
if (r>mid){
update(2*u+1,mid+1,t,l,r,k);
}
sum[u]=(sum[2*u]+sum[2*u+1])%mod;
return ;
}
ll query(int u,int s,int t,int l,int r){
if (l<=s && r>=t){
return sum[u]%=mod;
}
if(s>r|| t<l) return 0;
int mid=(s+t)>>1;
ll ans=0;
if (mid>=l){
ans+=query(2*u,s,mid,l,r);
ans%=mod;
}
if (r>mid){
ans+=query(2*u+1,mid+1,t,l,r);
ans%=mod;
}
return ans%=mod;
}
ll query_sum(int u,int v){
ll ans=0;
while (top[u]!=top[v]){
if (deep[top[u]]<deep[top[v]]){
swap(u,v);
}
ans+=query(1,1,number,id[top[u]],id[u]);
u=fa[top[u]];
}
if (id[u]<id[v]){
swap(u,v);
}
ans+=query(1,1,number,id[v],id[u]);
return ans;
}
void update_path(int u,int v,int k){
while (top[u]!=top[v]){
if (deep[u]<deep[v]){
swap(u,v);
}
update(1,1,number,id[top[u]],id[u],k);
u=fa[top[u]];
}
if (id[u]<id[v]){
swap(u,v);
}
update(1,1,number,id[v],id[u],k);
}
int main()
{
int n,m,r,mod;
cin>>n>>m>>r>>mod;
for (int i=1;i<=n;i++){
cin>>ch[i];
}
for (int i=1;i<=n-1;i++){
int x,y;
cin>>x>>y;
add_edge(x,y),add_edge(y,x);
}
dfs1(r,0);
dfs2(r,r);
build(1,1,n);
while (m--){
int t,x,y,z;
cin>>t;
if (t==1){
cin>>x>>y>>z;
update_path(x,y,z%mod);
}
if (t==2){
cin>>x>>y;
cout<<query_sum(x,y)%mod<<endl;
}
if (t==3){
cin>>x>>y;
update(1,1,n,id[x],id[x]+size[x]-1,y%mod);
}
if (t==4){
cin>>x;
cout<<query(1,1,n,id[x],size[x]+id[x]-1)%mod<<endl;
}
}
return 0;
}