萌新第一次学树剖……求大佬们指点，谢谢力！

其余点均>=5ms顺利通过

#include <iostream>
#include <cstring>

using namespace std;

//const int MAXN = 50;
const int MAXN = 100010;

long long cnter;

inline int LS(int x) {
	return x << 1;
}

inline int RS(int x) {
	return ((x << 1) | 1);
}

inline int LEN(int l, int r) {
	return r - l + 1;
}

inline int MID(int l, int r) {
	return l + ((r - l) >> 1);
}

int n, m, r, p;
int wSorted[MAXN];

class SegTree {
	public:
		SegTree() {};
		SegTree(int l, int r, int raw[]) {
			memset(data, 0, sizeof(data));
			memset(lazy, 0, sizeof(lazy));
			Builder(l, r, 1, raw);
			length = LEN(l, r);
			size = length * 4;
		}

		void Print() {
			cout << "Data: ";
			for (int i = 1; i <= size; ++i)
				cout << data[i] << ' ';
			cout << '\n'
			     << "Lazy: ";
			for (int i = 1; i <= size; ++i)
				cout << lazy[i] << ' ';
			return;
		}

		void Update(int l, int r, int k) {
			Updater(l, r, k, 1, 1, length);
			return;
		}
		int Query(int l, int r) {
			return Querier(l, r, 1, 1, length);
		}

	private:
		int data[4 * MAXN], lazy[4 * MAXN];
		int size, length;

		void Builder(int l, int r, int nowp, int raw[]) {
			if (l == r) {
				data[nowp] = raw[l] % p;
				return;
			}
			int mid = MID(l, r);
			Builder(l, mid, LS(nowp), raw);
			Builder(mid + 1, r, RS(nowp), raw);
			data[nowp] = (data[LS(nowp)] + data[RS(nowp)]) % p;
			return;
		}
		inline void PushDown(int nowp, int nowl, int nowr) {
			if (lazy[nowp] != 0) {
				int mid = MID(nowl, nowr);
				lazy[LS(nowp)] += lazy[nowp];
				lazy[RS(nowp)] += lazy[nowp];
				lazy[LS(nowp)] %= p;
				lazy[RS(nowp)] %= p;
				data[LS(nowp)] += lazy[nowp] * LEN(nowl, mid) % p;
				data[RS(nowp)] += lazy[nowp] * LEN(mid + 1, nowr) % p;
				data[LS(nowp)] %= p;
				data[RS(nowp)] %= p;
				lazy[nowp] = 0;
			}
			return;
		}
		void Updater(int l, int r, int k, int nowp, int nowl, int nowr) {
			if (nowl > r || nowr < l)
				return;
			else if (nowl >= l && nowr <= r) {
				data[nowp] += (k * LEN(nowl, nowr)) % p;
				data[nowp] %= p;
				if (nowl != nowr)
					lazy[nowp] += k, lazy[nowp] %= p;
			} else {
				int mid = MID(nowl, nowr);
				PushDown(nowp, nowl, nowr);
				Updater(l, r, k, LS(nowp), nowl, mid);
				Updater(l, r, k, RS(nowp), mid + 1, nowr);
				data[nowp] = (data[LS(nowp)] + data[RS(nowp)]) % p;
			}
			return;
		}
		int Querier(int l, int r, int nowp, int nowl, int nowr) {
			if (nowl > r || nowr < l)
				return 0;
			else if (nowl >= l && nowr <= r)
				return data[nowp] % p;
			else {
				int mid = MID(nowl, nowr);
				PushDown(nowp, nowl, nowr);
				return (Querier(l, r, LS(nowp), nowl, mid) + Querier(l, r, RS(nowp), mid + 1, nowr)) % p;
			}
		}
};

struct Graph {
	int e[MAXN], nxt[MAXN], first[MAXN], cnt, tim;
	int pointw[MAXN], fa[MAXN], dep[MAXN], siz[MAXN], hson[MAXN], dfn[MAXN], top[MAXN];

	Graph() {
		memset(dep, 0, sizeof(dep));
		memset(hson, -1, sizeof(hson));
		memset(nxt, -1, sizeof(nxt));
		memset(first, -1, sizeof(first));
		cnt = 0;
		tim = 0;
	}
	void Insert(int u, int v) {
		cnt++;
		e[cnt] = v;
		nxt[cnt] = first[u];
		first[u] = cnt;
	}
	void dfs1(int nowp, int f);
	void dfs2(int nowp, int top);
	void CUpdate(int x, int y, int k);
	int CQuery(int x, int y);
};

SegTree *tr;
Graph *gr;

inline void TUpdate(SegTree *t, Graph *g, int pos, int k) {
	k %= p;
	t->Update(g->dfn[pos], g->dfn[pos] + g->siz[pos] - 1, k);
	return;
}

inline int TQuery(SegTree *t, Graph *g, int pos) {
	return t->Query(g->dfn[pos], g->dfn[pos] + g->siz[pos] - 1) % p;
}

inline void read(int &x) {
	x = 0;
	int w = 1, ch = getchar();
	while (!isdigit(ch) && ch != '-')ch = getchar();
	if (ch == '-')w = -1, ch = getchar();
	while (isdigit(ch))x = (x << 3) + (x << 1) + (ch^'0'), ch = getchar();
	x = x * w;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

#ifndef ONLINE_JUDGE
//	freopen("P3384.in", "r", stdin);
//	freopen("outer.out", "w", stdout);
#endif

	int tu, tv, opt, tx, ty, tz;
	gr = new Graph();

//	cin >> n >> m >> r >> p;
	read(n);
	read(m);
	read(r);
	read(p);
	for (int i = 1; i <= n; i++)
		read(gr->pointw[i]);
	for (int i = 1; i < n; i++) {
		read(tu);
		read(tv);
		gr->Insert(tu, tv);
		gr->Insert(tv, tu);
	}

	gr->dfs1(r, r);
	gr->dfs2(r, r);
	tr = new SegTree(1, n, wSorted);

	for (int i = 1; i <= m; i++) {
		read(opt);
		switch (opt) {
			case 1:
//				cin >> tx >> ty >> tz;
				read(tx);
				read(ty);
				read(tz);
				tz %= p;
				gr->CUpdate(tx, ty, tz);
				break;
			case 2:
				read(tx);
				read(ty);
				cout << gr->CQuery(tx, ty) << '\n';
				break;
			case 3:
				read(tx);
				read(ty);
				TUpdate(tr, gr, tx, ty);
				break;
			case 4:
				read(tx);
				cout << TQuery(tr, gr, tx) << '\n';
				break;
		}
	}
	return 0;
}

void Graph::dfs1(int nowp, int f) {
	fa[nowp] = f;
	dep[nowp] = dep[f] + 1;
	siz[nowp] = 1;
	int heavySonSize = 0;
	for (int i = first[nowp]; i != -1; i = nxt[i]) {
		int v = e[i];
		if (v == f)
			continue;
		dfs1(v, nowp);
		siz[nowp] += siz[v];
		if (siz[v] > heavySonSize) {
			hson[nowp] = v;
			heavySonSize = siz[v];
		}
	}
	return;
}

void Graph::dfs2(int nowp, int topa) {
	tim++;
	dfn[nowp] = tim;
	top[nowp] = topa;
	wSorted[tim] = pointw[nowp];
	if (hson[nowp] == -1)
		return;
	dfs2(hson[nowp], topa);
	for (int i = first[nowp]; i != -1; i = nxt[i]) {
		int v = e[i];
		if (v != fa[nowp] && v != hson[nowp])
			dfs2(v, v);
	}
	return;
}

void Graph::CUpdate(int x, int y, int k) {
	cnter++;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]])
			swap(x, y);
		tr->Update(dfn[top[x]], dfn[x], k);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	tr->Update(dfn[x], dfn[y], k);
}

int Graph::CQuery(int x, int y) {
	int sum = 0;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]])
			swap(x, y);
		sum += tr->Query(dfn[top[x]], dfn[x]);
		sum %= p;
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	sum += tr->Query(dfn[x], dfn[y]);
	sum %= p;
	return sum;
}

谢谢喵！