- it
- 树链剖分板子
#include<iostream>
#define p1 p << 1
#define p2 p << 1 | 1
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std
;
const int N
= 100050;
ll sum
[N
<<3], add_t
[N
<<3];
int l_t
[N
<<3], r_t
[N
<<3];
ll
read(void) {
ll x
= 0, f
= 1;
char c
= getchar();
while (!isdigit(c
)) {
if (c
== '-') f
= -1;
c
= getchar();
}
while (isdigit(c
)) {
x
= (x
<< 3) + (x
<< 1) + c
- '0';
c
= getchar();
}
return x
* f
;
}
int siz
[N
], top
[N
];
int f
[N
], dep
[N
], son
[N
];
int h
[N
], to
[N
<<1];
int ne
[N
<<1], tot
;
ll w
[N
];
inline void add_e(int x
,int y
) {
ne
[++tot
] = h
[x
];
h
[x
] = tot
;
to
[tot
] = y
;
}
void dfs1(int x
,int fa
) {
dep
[x
] = dep
[fa
] + 1;
siz
[x
] = 1;
f
[x
] = fa
;
for (int i
= h
[x
]; i
; i
= ne
[i
]) {
int y
= to
[i
];
if (y
== fa
) continue;
dfs1(y
, x
);
siz
[x
] += siz
[y
];
if (siz
[y
] > siz
[son
[x
]]) son
[x
] = y
;
}
}
ll wt
[N
], cnt
;
int id
[N
], Top
[N
];
void dfs2(int x
,int topf
) {
id
[x
] = ++cnt
;
wt
[cnt
] = w
[x
];
Top
[x
] = topf
;
if (!son
[x
]) return;
dfs2(son
[x
], topf
);
for (int i
= h
[x
]; i
; i
= ne
[i
]) {
int y
= to
[i
];
if (y
== f
[x
] || y
== son
[x
]) continue;
dfs2(y
, y
);
}
}
ll n
, m
, r
, P
;
void buil(int l
,int r
,int p
) {
l_t
[p
] = l
, r_t
[p
] = r
;
if (l
== r
) {
sum
[p
] = wt
[l
] % P
;
return;
}
int mid
= (l
+ r
) >> 1;
buil(l
, mid
, p1
);
buil(mid
+ 1, r
, p2
);
sum
[p
] = sum
[p1
] + sum
[p2
];
}
void spread(int p
) {
if (add_t
[p
]) {
sum
[p1
] += (ll
)(r_t
[p1
] - l_t
[p1
] + 1) * add_t
[p
];
sum
[p2
] += (ll
)(r_t
[p2
] - l_t
[p2
] + 1) * add_t
[p
];
add_t
[p1
] += add_t
[p
];
add_t
[p2
] += add_t
[p
];
sum
[p1
] %= P
;
sum
[p2
] %= P
;
add_t
[p1
] %= P
;
add_t
[p2
] %= P
;
add_t
[p
]= 0;
}
}
void add(int l
,int r
,ll d
,int p
) {
if (l_t
[p
] >= l
&& r_t
[p
] <= r
) {
sum
[p
] += (r_t
[p
] - l_t
[p
] + 1) * d
;
sum
[p
] %= P
;
add_t
[p
] += d
;
return;
}
spread(p
);
if (l
<= r_t
[p1
]) add(l
, r
, d
, p1
);
if (r
>= l_t
[p2
]) add(l
, r
, d
, p2
);
sum
[p
] = sum
[p1
] + sum
[p2
];
sum
[p
] %= P
;
}
ll
ask(int l
,int r
,int p
) {
if (l_t
[p
] >= l
&& r_t
[p
] <= r
)
return sum
[p
];
spread(p
);
ll ans
= 0;
if (r_t
[p1
] >= l
) ans
+= ask(l
, r
, p1
);
if (l_t
[p2
] <= r
) ans
+= ask(l
, r
, p2
);
return ans
% P
;
}
void update(int x
,int y
,ll z
) {
while (Top
[x
] != Top
[y
]) {
if (dep
[Top
[x
]] < dep
[Top
[y
]]) swap(x
, y
);
add(id
[Top
[x
]], id
[x
], z
, 1);
x
= f
[Top
[x
]];
}
if (dep
[x
] < dep
[y
]) swap(x
, y
);
add(id
[y
], id
[x
], z
, 1);
}
ll
query(int x
,int y
) {
ll ans
= 0;
while (Top
[x
] != Top
[y
]) {
if (dep
[Top
[x
]] < dep
[Top
[y
]]) swap(x
, y
);
ans
+= ask(id
[Top
[x
]], id
[x
], 1);
x
= f
[Top
[x
]];
}
if (dep
[x
] < dep
[y
]) swap(x
, y
);
ans
+= ask(id
[y
], id
[x
], 1);
return ans
% P
;
}
void add_w(int x
,ll z
) {
add(id
[x
], id
[x
] + siz
[x
] - 1, z
, 1);
}
ll
query_w(int x
) {
return ask(id
[x
], id
[x
] + siz
[x
] - 1, 1) % P
;
}
int main() {
n
= read(), m
= read(), r
= read(), P
= read();
for (int i
= 1;i
<= n
; i
++) w
[i
] = read();
for (int i
= 1;i
< n
; i
++) {
int x
= read(), y
= read();
add_e(x
, y
); add_e(y
, x
);
}
dfs1(r
, 0);
dfs2(r
, r
);
buil(1, n
, 1);
for (int i
= 1;i
<= m
; i
++) {
int op
= read();
if (op
== 1) {
int x
= read(), y
= read();
ll z
= read() % P
;
update(x
, y
, z
);
}
else if (op
== 2) {
int x
= read(), y
= read();
printf
("%lld\n", query(x
, y
));
}
else if (op
== 3) {
int x
= read();
ll z
= read();
add_w(x
, z
% P
);
}
else {
int x
= read();
printf
("%lld\n", query_w(x
));
}
}
return 0;
}
