1 #pragma comment(linker, "/STACK:1024000000,1024000000")
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <cmath>
6 #include <ctime>
7 #include <cctype>
8 #include <climits>
9 #include <iostream>
10 #include <iomanip>
11 #include <algorithm>
12 #include <string>
13 #include <sstream>
14 #include <stack>
15 #include <queue>
16 #include <set>
17 #include <map>
18 #include <vector>
19 #include <list>
20 #include <fstream>
21 #define ri readint()
22 #define gc getchar()
23 #define R(x) scanf("%d", &x)
24 #define W(x) printf("%d
", x)
25 #define init(a, b) memset(a, b, sizeof(a))
26 #define rep(i, a, b) for (int i = a; i <= b; i++)
27 #define irep(i, a, b) for (int i = a; i >= b; i--)
28 #define ls p << 1
29 #define rs p << 1 | 1
30 using namespace std;
31
32 typedef double db;
33 typedef long long ll;
34 typedef unsigned long long ull;
35 typedef pair<int, int> P;
36 const int inf = 0x3f3f3f3f;
37 const ll INF = 1e18;
38
39 inline int readint() {
40 int x = 0, s = 1, c = gc;
41 while (c <= 32) c = gc;
42 if (c == '-') s = -1, c = gc;
43 for (; isdigit(c); c = gc)
44 x = x * 10 + c - 48;
45 return x * s;
46 }
47
48 const int maxn = 1e5 + 5;
49 int n, m, root, mod, a[maxn];
50 int deep[maxn], fa[maxn], size[maxn], son[maxn], top[maxn], id[maxn], rnk[maxn], cnt;
51
52 struct Edge {
53 int to, nxt;
54 }e[maxn << 1];
55 int tot, head[maxn];
56
57 struct Seg {
58 int l, r, sum, laz;
59 }t[maxn << 2];
60
61 inline void add(int u, int v) {
62 e[++tot].to = v, e[tot].nxt = head[u], head[u] = tot;
63 }
64
65 inline int len(int p) {
66 return t[p].r - t[p].l + 1;
67 }
68
69 inline void push_up(int p) {
70 t[p].sum = (t[ls].sum + t[rs].sum) % mod;
71 }
72
73 inline void push_down(int p) {
74 if (t[p].laz) {
75 t[ls].laz += t[p].laz;
76 t[rs].laz += t[p].laz;
77 t[ls].sum = (t[ls].sum + len(ls) * t[p].laz % mod) % mod;
78 t[rs].sum = (t[rs].sum + len(rs) * t[p].laz % mod) % mod;
79 t[p].laz = 0;
80 }
81 }
82
83 void build(int l, int r, int p) {
84 t[p].l = l, t[p].r = r;
85 if (l == r) {
86 t[p].laz = 0;
87 t[p].sum = rnk[l];
88 return;
89 }
90 int mid = (l + r) >> 1;
91 build(l, mid, ls);
92 build(mid + 1, r, rs);
93 push_up(p);
94 }
95
96 void segupd(int l, int r, int p, int k) {
97 if (l <= t[p].l && t[p].r <= r) {
98 t[p].sum = (t[p].sum + len(p) * k % mod) % mod;
99 t[p].laz += k;
100 return;
101 }
102 int mid = (t[p].l + t[p].r) >> 1;
103 push_down(p);
104 if (l <= mid) segupd(l, r, ls, k);
105 if (mid < r) segupd(l, r, rs, k);
106 push_up(p);
107 }
108
109 int segask(int l, int r, int p) {
110 if (l <= t[p].l && t[p].r <= r) return t[p].sum;
111 int mid = (t[p].l + t[p].r) >> 1;
112 int res = 0;
113 push_down(p);
114 if (l <= mid) res = (res + segask(l, r, ls)) % mod;
115 if (mid < r) res = (res + segask(l, r, rs)) % mod;
116 return res;
117 }
118
119 void dfs1(int u, int f, int depth) {//得到重儿子及一些普通信息
120 deep[u] = depth;
121 fa[u] = f;
122 size[u] = 1;
123 for (int i = head[u]; i; i = e[i].nxt) {
124 int v = e[i].to;
125 if (v == f) continue;
126 dfs1(v, u, depth + 1);
127 if (size[v] > size[son[u]]) son[u] = v;
128 size[u] += size[v];
129 }
130 }
131
132 void dfs2(int u, int topf) {//将重链排列在一起以便线段树维护
133 id[u] = ++cnt;
134 rnk[cnt] = a[u];
135 top[u] = topf;
136 if (!son[u]) return;
137 dfs2(son[u], topf);
138 for (int i = head[u]; i; i = e[i].nxt) {
139 int v = e[i].to;
140 if (v != son[u] && v != fa[u])
141 dfs2(v, v);
142 }
143 }
144
145 void Update(int x, int y, int z) {//类似倍增的方式
146 while (top[x] != top[y]) {
147 if (deep[top[x]] < deep[top[y]]) swap(x, y);
148 segupd(id[top[x]], id[x], 1, z);
149 x = fa[top[x]];
150 }
151 if (deep[x] > deep[y]) swap(x, y);
152 segupd(id[x], id[y], 1, z);
153 }
154
155 int Query(int x, int y) {
156 int ans = 0;
157 while (top[x] != top[y]) {
158 if (deep[top[x]] < deep[top[y]]) swap(x, y);
159 ans = (ans + segask(id[top[x]], id[x], 1)) % mod;
160 x = fa[top[x]];
161 }
162 if (deep[x] > deep[y]) swap(x, y);
163 ans = (ans + segask(id[x], id[y], 1)) % mod;
164 return ans;
165 }
166
167 int main() {
168 n = ri, m = ri, root = ri, mod = ri;
169 rep(i, 1, n) {
170 a[i] = ri;
171 a[i] %= mod;
172 }
173 rep(i, 1, n - 1) {
174 int x = ri, y = ri;
175 add(x, y);
176 add(y, x);
177 }
178 dfs1(root, 0, 1);
179 dfs2(root, root);
180 build(1, n, 1);
181
182 while (m--) {
183 int op = ri, x, y, z;
184 if (op == 1) {
185 x = ri, y = ri, z = ri;
186 Update(x, y, z % mod);//从x到y的最短路径上的节点都加z
187 } else if (op == 2) {
188 x = ri, y = ri;
189 W(Query(x, y));//查询x到y的最短路节点和
190 } else if (op == 3) {
191 x = ri, z = ri;
192 segupd(id[x], id[x] + size[x] - 1, 1, z % mod);//对x的子树全加z
193 } else {
194 x = ri;
195 W(segask(id[x], id[x] + size[x] - 1, 1));//查询x的子树节点和
196 }
197 }
198 return 0;
199 }
