1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
| #include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,w=0;char c=getchar();
while(!isdigit(c)) w|=c=='-',c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=1e5+10,maxm=1e5+10;
int n,m,root,mod;
int fa[maxn],dep[maxn],son[maxn],siz[maxn],top[maxn],dfn[maxn],a[maxn],w[maxn];
int ecnt,head[maxn],to[maxn<<1],nxt[maxn<<1];
inline void addedge(int a,int b){
to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;
to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;
}
struct SegmentTree{
#define ls (ro<<1)
#define rs (ro<<1|1)
#define mid ((l+r)>>1)
int val[maxn<<2],tag[maxn<<2];
inline void pushup(int ro){val[ro]=(val[ls]+val[rs])%mod;}
inline void pushdown(int ro,int l,int r){
tag[ls]+=tag[ro],val[ls]=(val[ls]+(mid-l+1)*tag[ro])%mod;
tag[rs]+=tag[ro],val[rs]=(val[rs]+(r-mid)*tag[ro])%mod;
tag[ro]=0;
}
void build(const int &ro=1,const int &l=1,const int &r=n){
if(l==r) return val[ro]=w[l]%mod,void();
build(ls,l,mid),build(rs,mid+1,r);
pushup(ro);
}
void update(int x,int y,int k,const int &ro=1,const int &l=1,const int &r=n){
if(x==l and y==r) return tag[ro]+=k,val[ro]=(val[ro]+k*(r-l+1))%mod,void();
if(tag[ro]) pushdown(ro,l,r);
if(y<=mid) update(x,y,k,ls,l,mid);
else if(x>mid) update(x,y,k,rs,mid+1,r);
else update(x,mid,k,ls,l,mid),update(mid+1,y,k,rs,mid+1,r);
pushup(ro);
}
int query(int x,int y,const int &ro=1,const int &l=1,const int &r=n){
if(x==l and y==r) return val[ro];
if(tag[ro]) pushdown(ro,l,r);
if(y<=mid) return query(x,y,ls,l,mid);
if(x>mid) return query(x,y,rs,mid+1,r);
return (query(x,mid,ls,l,mid)+query(mid+1,y,rs,mid+1,r))%mod;
}
#undef ls
#undef rs
#undef mid
}st;
void dfs1(int x,int Fa){
fa[x]=Fa,siz[x]=1,dep[x]=dep[Fa]+1;
int mx=-1;
for(int u,i=head[x];i;i=nxt[i]) if((u=to[i])!=Fa){
dfs1(u,x);
siz[x]+=siz[u];
if(siz[u]>mx) son[x]=u,mx=siz[u];
}
}
void dfs2(int x,int topf){
w[dfn[x]=++dfn[0]]=a[x];
top[x]=topf;
if(!son[x]) return;
dfs2(son[x],topf);
for(int u,i=head[x];i;i=nxt[i]) if((u=to[i])!=fa[x] and u!=son[x]) dfs2(u,u);
}
inline void update(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
st.update(dfn[top[x]],dfn[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
st.update(dfn[x],dfn[y],k);
}
inline int query(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans=(ans+st.query(dfn[top[x]],dfn[x]))%mod;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans=(ans+st.query(dfn[x],dfn[y]))%mod;
return ans;
}
inline void work(){
n=read(),m=read(),root=read(),mod=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<n;i++) addedge(read(),read());
dfs1(root,root),dfs2(root,root);
st.build();
while(m--){
int a,b,c;
switch(read()){
case 1:{
a=read(),b=read(),c=read()%mod;
update(a,b,c);
break;
}
case 2:{
printf("%d\n",query(read(),read()));
break;
}
case 3:{
a=read(),b=read();
st.update(dfn[a],dfn[a]+siz[a]-1,b);
break;
}
case 4:{
a=read();
printf("%d\n",st.query(dfn[a],dfn[a]+siz[a]-1));
break;
}
}
}
}
}
signed main(){
star::work();
return 0;
}
|
