const int MAXN = 1e5 + 5; // 最大节点数 int N, M, R, P; // 节点数、操作数、根节点、模数 vector adj[MAXN]; // 邻接表存储树结构 int val[MAXN]; // 节点初始权值 // 树链剖分相关变量 int parent[MAXN]; // 父节点 int depth[MAXN]; // 节点深度 int sz[MAXN]; // 子树大小 int heavy[MAXN]; // 重儿子 int pos[MAXN]; // 节点在线段树中的位置 int top[MAXN]; // 所在重链的顶部节点 int current_pos; // 当前DFS序位置 // 线段树节点结构 struct node { int data; // 节点值 int lazy; // 懒标记 node() : data(0), lazy(0) {} }; vector tree; // 线段树 // 构建线段树 void build(const vector& datas, vector& tree, int rt, int left, int right) { if (left == right) { tree[rt].data = datas[left]; return; } int mid = left + (right - left) / 2; build(datas, tree, 2 * rt, left, mid); build(datas, tree, 2 * rt + 1, mid + 1, right); tree[rt].data = (tree[2 * rt].data + tree[2 * rt + 1].data) % P; } // 下传懒标记 void pushDown(vector& tree, int rt, int len) { if (tree[rt].lazy != 0) { tree[rt * 2].data = (tree[rt * 2].data + tree[rt].lazy * (len - len / 2)) % P; tree[rt * 2].lazy = (tree[rt * 2].lazy + tree[rt].lazy) % P; tree[rt * 2 + 1].data = (tree[rt * 2 + 1].data + tree[rt].lazy * (len / 2)) % P; tree[rt * 2 + 1].lazy = (tree[rt * 2 + 1].lazy + tree[rt].lazy) % P; tree[rt].lazy = 0; } } // 线段树区间查询 int query(vector& tree, int rt, int left, int right, int ql, int qr) { if (ql > right || qr < left) { return 0; } if (ql <= left && qr >= right) { return tree[rt].data; } pushDown(tree, rt, right - left + 1); int mid = left + (right - left) / 2; int leftsum = query(tree, 2 * rt, left, mid, ql, qr); int rightsum = query(tree, 2 * rt + 1, mid + 1, right, ql, qr); return (leftsum + rightsum) % P; } // 线段树区间更新 void updateRange(vector& tree, int rt, int left, int right, int ul, int ur, int value) { if (ul > right || ur < left) return; if (ul <= left && ur >= right) { tree[rt].data = (tree[rt].data + value * (right - left + 1)) % P; tree[rt].lazy = (tree[rt].lazy + value) % P; return; } pushDown(tree, rt, right - left + 1); int mid = left + (right - left) / 2; updateRange(tree, 2 * rt, left, mid, ul, ur, value); updateRange(tree, 2 * rt + 1, mid + 1, right, ul, ur, value); tree[rt].data = (tree[2 * rt].data + tree[2 * rt + 1].data) % P; } // 第一次DFS:计算父节点、深度、子树大小和重儿子 void dfs1(int u, int p) { parent[u] = p; depth[u] = depth[p] + 1; sz[u] = 1; heavy[u] = 0; for (int v : adj[u]) { if (v != p) { dfs1(v, u); sz[u] += sz[v]; if (sz[v] > sz[heavy[u]]) { heavy[u] = v; } } } } // 第二次DFS:进行重链剖分,计算DFS序和重链顶部 void dfs2(int u, int p, int chain_top) { pos[u] = ++current_pos; top[u] = chain_top; if (heavy[u]) { dfs2(heavy[u], u, chain_top); } for (int v : adj[u]) { if (v != p && v != heavy[u]) { dfs2(v, u, v); } } } // 路径更新:将x到y路径上的节点值都加上z void pathUpdate(int x, int y, int z) { while (top[x] != top[y]) { if (depth[top[x]] > depth[top[y]]) { swap(x, y); } updateRange(tree, 1, 1, N, pos[top[y]], pos[y], z); y = parent[top[y]]; } if (depth[x] > depth[y]) { swap(x, y); } updateRange(tree, 1, 1, N, pos[x], pos[y], z); } // 路径查询:查询x到y路径上的节点值之和 int pathQuery(int x, int y) { int res = 0; while (top[x] != top[y]) { if (depth[top[x]] > depth[top[y]]) { swap(x, y); } res = (res + query(tree, 1, 1, N, pos[top[y]], pos[y])) % P; y = parent[top[y]]; } if (depth[x] > depth[y]) { swap(x, y); } res = (res + query(tree, 1, 1, N, pos[x], pos[y])) % P; return res; } // 子树更新:将以x为根的子树所有节点值加上z void subtreeUpdate(int x, int z) { int l = pos[x]; int r = pos[x] + sz[x] - 1; updateRange(tree, 1, 1, N, l, r, z); } // 子树查询:查询以x为根的子树所有节点值之和 int subtreeQuery(int x) { int l = pos[x]; int r = pos[x] + sz[x] - 1; return query(tree, 1, 1, N, l, r); } // 求两个节点的最近公共祖先(LCA) int lca(int x, int y) { while (top[x] != top[y]) { if (depth[top[x]] < depth[top[y]]) { swap(x, y); } x = parent[top[x]]; } return depth[x] < depth[y] ? x : y; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M >> R >> P; for (int i = 1; i <= N; ++i) { cin >> val[i]; } for (int i = 1; i < N; ++i) { int x, y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } // 第一次DFS预处理 dfs1(R, 0); current_pos = 0; // 第二次DFS进行重链剖分 dfs2(R, 0, R); // 构建线段树 vector datas(N + 1); for (int i = 1; i <= N; ++i) { datas[pos[i]] = val[i] % P; } tree.resize(4 * (N + 1)); build(datas, tree, 1, 1, N); // 处理操作 while (M--) { int cmd; cin >> cmd; if (cmd == 1) { // 路径更新 int x, y, z; cin >> x >> y >> z; pathUpdate(x, y, z); } else if (cmd == 2) { // 路径查询 int x, y; cin >> x >> y; cout << pathQuery(x, y) << '\n'; } else if (cmd == 3) { // 子树更新 int x, z; cin >> x >> z; subtreeUpdate(x, z); } else if (cmd == 4) { // 子树查询 int x; cin >> x; cout << subtreeQuery(x) << '\n'; } } return 0; }