就这个树链剖分模板， 样例都过不了（

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct TreeNode {
	int l, r, sum, tag;
} tr[N];
int depth[N], fa[N], size[N], son[N], id[N], top[N], nw[N], w[N], cnt;
int n, m, root, mod;
vector<int> edge[N];


/*-----------------------------------------------------------------*/


inline void pushdown (int p) {
	if (tr[p].tag) {
		int l = p << 1 , r = p << 1 | 1;
		tr[l].tag += tr[p].tag;
		tr[r].tag += tr[p].tag;
		tr[l].sum += tr[p].tag * (tr[p].r - tr[p].l + 1) % mod;
		tr[r].sum += tr[p].tag * (tr[p].r - tr[p].l + 1) % mod;
		tr[p].tag = 0;
	}
}

inline void build (int p, int l , int r) {
	tr[p].l = l;
	tr[p].r = r;
	if (l == r) {
		tr[p].sum = nw[l] % mod;
		return ;
	}
	int mid = l + r >> 1;
	build (p << 1, l, mid);
	build (p << 1 | 1, mid + 1, r);
	tr[p].sum = (tr[p << 1].sum + tr[p << 1 | 1].sum) % mod;
}

inline int query (int p, int x, int y) {
	if (x <= tr[p].l && tr[p].r <= y) return tr[p].sum % mod;
	pushdown (p);
	int mid = tr[p].l + tr[p].r >> 1;
	if (x <= mid) return query (p << 1, x, y);
	if (y > mid) return query (p << 1 | 1, x, y);
}

inline void add (int p, int x, int y, int z) {
	z %= mod;
	if (x <= tr[p].l && tr[p].r <= y) {
		tr[p].sum += z * (tr[p].r - tr[p].l + 1) %mod;
		tr[p].tag += z;
		return;
	}
	pushdown (p);
	int mid = tr[p].l + tr[p].r >> 1;
	if (x <= mid) add (p << 1, x, y, z);
	if (y > mid) add (p << 1 | 1, x, y, z);
	tr[p].sum = (tr[p << 1].sum + tr[p << 1 | 1].sum) % mod;
}


/*-----------------------------------------------------------------*/

inline void dfs1 (int u, int fath) {
	fa[u] = fath;
	depth[u] = depth[fath] + 1;
	size[u] = 1;
	for (int i = 0; i < edge[u].size(); i ++) {
		int v = edge[u][i];
		if (v != fath) {
			dfs1 (v, u);
			size[u] += size[v];
			if (size[v] > size[son[u]]) son[u] = v;
		}
	}
}

inline void dfs2 (int u, int t) {
	top[u] = t;
	id[u] = ++ cnt;
	nw[cnt] = w[u];
	if (!son[u]) return;
	dfs2 (son[u], t);
	for (int i = 0; i < edge[u].size(); i ++) {
		int v = edge[u][i];
		if (v != fa[u] && v != son[u]) dfs2 (v, v);
	}
}

inline int Rquery (int x, int y) {
	int ans = 0;
	while (top[x] != top[y]) {
		if (depth[top[x]] < depth[top[y]]) swap (x, y);
		ans += query (1, id[top[x]], id[x]);
		x = fa[top[x]];
	}
	if (depth[x] > depth[y]) swap (x, y);
	return (ans + query (1, id[x], id[y])) % mod;
}

inline void Radd (int x, int y, int z) {
	z %= mod;
	while (top[x] != top[y]) {
		if (depth[top[x]] < depth[top[y]]) swap (x, y);
		add (1, id[top[x]], id[x], z);
		x = fa[top[x]];
	}
	if (depth[x] > depth[y]) swap (x, y);
	add (1, id[x], id[y], z);
}

inline int Squery (int p) {
	int ans = 0;
	ans += query (1, id[p], id[p] + size[p] - 1);
	return ans;
}

inline void Sadd (int p, int k) {
	add (1, id[p], id[p] + size[p] - 1, k);
}


/*-----------------------------------------------------------------*/


inline int read () {
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); }
	return x * f;
}

int main() {
	n = read(); m = read(); root = read(); mod = read();
	for (int i = 1; i <= n; i ++) w[i] = read();
	for (int i = 1; i < n; i ++) {
		int a, b;
		a = read(); b = read();
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	dfs1 (root , 0);
	dfs2 (root , root);
	build (1, 1, n);
	int opt, x, y, z;
	for (int i = 1; i <= n; i ++) cout << id[i] << ' ';
	cout << '\n';
	for (int i = 1; i <= n; i ++) cout << nw[i] << ' ';
	cout << '\n';
	for (int i = 1; i <= m; i ++) {
		opt = read();
		if (opt == 1) {
			x = read(); y = read(); z = read();
			Radd (x, y, z);
		} else if (opt == 2) {
			x = read(); y = read();
			printf ("%d\n", Rquery (x, y));
		} else if (opt == 3) {
			x = read(); y = read();
			Sadd (x, y);
		} else if (opt == 4) {
			x = read();
			printf ("%d\n", Squery (x));
		}
	}
	return 0;
}

啊啊啊这东西是谁发明的