const int MAXN = 1e5 + 5; // 最大节点数
int N, M, R, P; // 节点数、操作数、根节点、模数
vector<int> 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<node> tree; // 线段树
// 构建线段树
void build(const vector<int>& datas, vector<node>& 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<node>& 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<node>& 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<node>& 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<int> 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;
}const int MAXN = 1e5 + 5; // 最大节点数
int N, M, R; // 节点数、操作数、根节点
vector<int> 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<node> tree; // 线段树
// 构建线段树
void build(const vector<int>& datas, vector<node>& 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;
}
// 下传懒标记
void pushDown(vector<node>& tree, int rt, int len) {
if (tree[rt].lazy != 0) {
tree[rt * 2].data = tree[rt * 2].data + tree[rt].lazy * (len - len / 2);
tree[rt * 2].lazy = tree[rt * 2].lazy + tree[rt].lazy;
tree[rt * 2 + 1].data = tree[rt * 2 + 1].data + tree[rt].lazy * (len / 2);
tree[rt * 2 + 1].lazy = tree[rt * 2 + 1].lazy + tree[rt].lazy;
tree[rt].lazy = 0;
}
}
// 线段树区间查询
int query(vector<node>& 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;
}
// 线段树区间更新
void updateRange(vector<node>& 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);
tree[rt].lazy = tree[rt].lazy + value;
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;
}
// 第一次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]);
y = parent[top[y]];
}
if (depth[x] > depth[y]) {
swap(x, y);
}
res = res + query(tree, 1, 1, N, pos[x], pos[y]);
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;
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<int> datas(N + 1);
for (int i = 1; i <= N; ++i) {
datas[pos[i]] = val[i];
}
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;
}