19分没过样例重链剖分唐氏代码悬关求调

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5;
struct SegmentTree {
	int l, r, val, lz;
};
int n, m, root, mod, val[N + 3];
int hson[N + 3], father[N + 3], size[N + 3], dep[N + 3], seg[N + 3], top[N + 3], rev[N + 3];
SegmentTree tree[(N << 2) + 3];
vector<int> G[N + 3];
void build(int p, int l, int r) {
	tree[p].l = l, tree[p].r = r, tree[p].lz = 0;
	if (l == r) {
		tree[p].val = val[rev[l]];
		return;
	}
	int mid = l + r >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	tree[p].val = (tree[p << 1].val + tree[p << 1 | 1].val) % mod;
	return;
}
void pushdown(int p) {
	if (tree[p].lz) {
		tree[p << 1].lz += tree[p].lz, tree[p << 1 | 1].lz += tree[p].lz;
		tree[p << 1].val = (tree[p << 1].val + tree[p].lz * (tree[p << 1].r - tree[p << 1].l + 1)) % mod;
		tree[p << 1 | 1].val = (tree[p << 1 | 1].val + tree[p].lz * (tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1)) % mod;
		tree[p].val = (tree[p << 1].val + tree[p << 1 | 1].val) % mod;
	}
}
void update_plus(int p, int l, int r, int k) {
	if (tree[p].r < l || tree[p].l > r) return;
	if (tree[p].l >= l && tree[p].r <= r) {
		tree[p].val = (tree[p].val + k * (tree[p].r - tree[p].l + 1)) % mod;
		tree[p].lz += k;
		return;
	}
	pushdown(p);
	if (tree[p << 1].r >= l) update_plus(p << 1, l, r, k);
	if (tree[p << 1 | 1].l <= r) update_plus(p << 1 | 1, l, r, k);
	tree[p].val = (tree[p << 1].val + tree[p << 1 | 1].val) % mod;
	return;
}
int query(int p, int l, int r) {
	if (tree[p].r < l || tree[p].l > r) return 0;
	if (tree[p].l >= l && tree[p].r <= r) return tree[p].val;
	pushdown(p);
	int ret = 0;
	if (tree[p << 1].r >= l) ret = (ret + query(p << 1, l, r)) % mod;
	if (tree[p << 1 | 1].l <= r) ret = (ret + query(p << 1 | 1, l, r)) % mod;
	return ret;
}
void dfs1(int u, int fa) {
	hson[u] = 0, father[u] = fa, size[u] = 1, dep[u] = dep[fa] + 1;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (v != fa) {
			dfs1(v, u);
			size[u] += size[v];
			if (size[v] > size[hson[u]]) hson[u] = v;
		}
	}
	return;
}
void dfs2(int u, int fa) {
	if (hson[u]) {
		seg[hson[u]] = ++seg[0], top[hson[u]] = top[u], rev[seg[0]] = hson[u];
		dfs2(hson[u], u);
	}
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (v != fa && !top[v]) {
			seg[v] = ++seg[0];
			top[v] = v;
			rev[seg[0]] = v;
			dfs2(v, u);
		}
	}
	return;
}
void update_path(int x, int y, int z) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		update_plus(1, seg[top[x]], seg[x], z);
		x = father[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	update_plus(1, seg[x], seg[y], z);
	return;
}
int query_path(int x, int y) {
	int ret = 0;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		ret = (ret + query(1, seg[top[x]], seg[x])) % mod;
		x = father[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	ret = (ret + query(1, seg[x], seg[y])) % mod;
	return ret;
}
void update_tree(int x, int y) {
	update_plus(1, seg[x], seg[x] + size[x] - 1, y);
	return;
}
int query_tree(int x) {
	return query(1, seg[x], seg[x] + size[x] - 1) % mod;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> root >> mod;
	for (int i = 1; i <= n; i++) cin >> val[i];
	for (int i = 1; i <= n - 1; i++) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	size[0] = 0, dep[root] = 0, seg[0] = seg[root] = 1, top[root] = root, rev[1] = root;
	dfs1(root, root);
	dfs2(root, root);
	build(1, 1, n);
	while (m--) {
		int op, x, y, z;
		cin >> op;
		switch (op) {
			case 1:
				cin >> x >> y >> z;
				update_path(x, y, z);
				break;
			case 2:
				cin >> x >> y;
				cout << query_path(x, y) << '\n';
				break;
			case 3:
				cin >> x >> y;
				update_tree(x, y);
				break;
			case 4:
				cin >> x;
				cout << query_tree(x) << '\n';
				break;
		}
	}
	return 0;
}