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
126
| inline void push_up(int p){
tr[p].w=tr[p<<1].w+tr[p<<1|1].w;
}
inline void push_down(int p){
if(!tr[p].lazy) return ;
tr[p<<1].w+=tr[p].lazy*(tr[p<<1].r-tr[p<<1].l+1);
tr[p<<1].lazy+=tr[p].lazy;
tr[p<<1|1].w+=tr[p].lazy*(tr[p<<1|1].r-tr[p<<1|1].l+1);
tr[p<<1|1].lazy+=tr[p].lazy;
tr[p].lazy=0;
}
void build(int p,int l,int r){
tr[p].l=l;tr[p].r=r;
if(l==r){
tr[p].w=w[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
push_up(p);
}
void add(int p,int l,int r,LL k){
if(tr[p].l==l&&tr[p].r==r)
{
tr[p].w+=(r-l+1)*k;
tr[p].lazy+=k;
return ;
}
push_down(p);
int mid=(tr[p].l+tr[p].r)>>1;
if(r<=mid) add(p<<1,l,r,k);
else if(l>mid) add(p<<1|1,l,r,k);
else{
add(p<<1,l,mid,k);add(p<<1|1,mid+1,r,k);
}
push_up(p);
}
LL query(int p,int l,int r){
if(tr[p].l==l&&tr[p].r==r)
{
return tr[p].w;
}
LL ans=0;
push_down(p);
int mid=(tr[p].l+tr[p].r)>>1;
if(r<=mid) ans=query(p<<1,l,r);
else if(l>mid) ans=query(p<<1|1,l,r);
else{
ans=query(p<<1,l,mid)+query(p<<1|1,mid+1,r);
}
push_up(p);
return ans;
}
void dfs_1(int x){
siz[x]=1;
for(int i=0;i<v[x].size();i++){
if(cur!=f[x]){
f[cur]=x;
deep[cur]=deep[x]+1;
dfs_1(cur);
siz[x]+=siz[cur];
if(siz[son[x]]<siz[cur]) son[x]=cur;
}
}
}
void dfs_2(int x,int p){
id[x]=++tot;w[tot]=d[x];top[x]=p;
if(son[x]) dfs_2(son[x],p);
for(int i=0;i<v[x].size();i++){
if(cur!=f[x]&&cur!=son[x]){
dfs_2(cur,cur);
}
}
}
void modify(int a,int b,int k){
while(top[a]!=top[b]){
if(deep[top[a]]>deep[top[b]]) swap(a,b);
add(1,id[top[b]],id[b],k);
b=f[top[b]];
}if(deep[a]>deep[b]) swap(a,b);
add(1,id[a],id[b],k);
}
LL find(int a,int b){
LL ans=0;
while(top[a]!=top[b]){
if(deep[top[a]]>deep[top[b]]) swap(a,b);
ans+=query(1,id[top[b]],id[b]); ans%=MOD;
b=f[top[b]];
}if(deep[a]>deep[b]) swap(a,b);
ans+=query(1,id[a],id[b]);
return ans%MOD;
}
int main()
{
int n,m,root;
n=get_num();m=get_num();root=get_num();MOD=get_num();
for(int i=1;i<=n;i++) d[i]=get_num();
for(int i=1;i<n;i++){
int a,b;
a=get_num();b=get_num();v[a].push_back(b);
v[b].push_back(a);
}
dfs_1(root);
dfs_2(root,root);
build(1,1,n);
int c,x,y;LL z;
for(int i=1;i<=m;i++){
c=get_num();x=get_num();
if(c==1){
y=get_num();
z=get_num();
modify(x,y,z%MOD);
}else if(c==2)
{
y=get_num();
cout<<find(x,y)<<'\n';
}else if(c==3){
z=get_num();
add(1,id[x],id[x]+siz[x]-1,z%MOD);
}else if(c==4){
cout<<query(1,id[x],id[x]+siz[x]-1)%MOD<<'\n';
}
}
return 0;
}
|
