洛谷 3384：【模板】轻重链剖分/树链剖分

#include <stdio.h>
#define size 100001
static int val[size], lawa[size], tawa[size << 1], kama[size << 1];
static int prefers[size], tops[size], s2g[size], g2s[size], sl[size];
static int seg[size * 6], lc[size * 6], rc[size * 6], tags[size * 6];
static int deps[size], mama[size];

int min(int u, int v)
{
	return u < v ? u : v;
}

int max(int u, int v)
{
	return u > v ? u : v;
}

int dfs1(int cur)
{
	int result = 1, i, hog = 0, sin;
	for (i = lawa[cur]; i; i = kama[i])
		if (tawa[i]) {
			mama[tawa[i]] = cur;
			tawa[i ^ 1] = 0;
			sin = dfs1(tawa[i]);
			if (sin > hog) {
				hog = sin;
				prefers[cur] = tawa[i];
			}
			result += sin;
		}
	return result;
}

void dfs2(int cur, int top, int depth)
{
	static int nseg = 0;
	int i, prefer = prefers[cur];
	deps[cur] = depth;
	tops[cur] = top;
	s2g[g2s[cur] = ++nseg] = cur;
	if (prefer)
		dfs2(prefer, top, depth);
	for (i = lawa[cur]; i; i = kama[i]) {
		int dest = tawa[i];
		if (dest && dest != prefer)
			dfs2(dest, /* top = */ dest, 1 + depth);
	}
	sl[cur] = nseg;
}

int seg_build(int ofirst, int olast)
{
	static int nseg = 0;
	int mid = (ofirst + olast) >> 1, now = ++nseg;
	if (ofirst >  olast)
		return 0;
	if (ofirst == olast) {
		seg[now] = val[s2g[ofirst]];
		return now;
	}
	lc[now]		= seg_build(ofirst, mid);
	rc[now]		= seg_build(1 + mid, olast);
	seg[now]	= seg[lc[now]] + seg[rc[now]];
	return now;
}

void seg_add(int p, long long int w,
		int first, int last, int ofirst, int olast, int rank)
{
	int mid = (ofirst + olast) >> 1;
	if (!p || first > olast || last < ofirst)
		return;
	if (first <= ofirst && last >= olast) {
		tags[p] = (tags[p] + w) % rank;
		return;
	}
	seg[p] = (seg[p] + w *
			(min(last, olast) - max(first, ofirst) + 1)) % rank;
	seg_add(lc[p], w, first, last, ofirst, mid, rank);
	seg_add(rc[p], w, first, last, 1 + mid, olast, rank);
}

int seg_sum(int p, int first, int last,
		long long int tag, int ofirst, int olast, int rank)
{
	int mid = (ofirst + olast) >> 1;
	tag = (tag + tags[p]) % rank;
	if (!p || first > olast || last < ofirst)
		return 0;
	if (first <= ofirst && last >= olast)
		return (tag * (olast - ofirst + 1) + seg[p]) % rank;
	return ((long long)
		seg_sum(lc[p], first, last, tag, ofirst, mid, rank) +
		seg_sum(rc[p], first, last, tag, 1 + mid, olast, rank)) % rank;
}

int main(void)
{
	int n, m, r, p, i, oseg;
	scanf("%d%d%d%d", &n, &m, &r, &p);
	for (i = 1; i <= n; ++i)	scanf("%d", i + val);
	for (i = 1; i < n; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		tawa[i << 1] = x;
		kama[i << 1] = lawa[y];
		lawa[y] = i << 1;
		tawa[i << 1 ^ 1] = y;
		kama[i << 1 ^ 1] = lawa[x];
		lawa[x] = i << 1 ^ 1;
	}
	dfs1(r);
	dfs2(r, r, 1);
	oseg = seg_build(1, n);
	for (i = 1; i <= m; ++i) {
		int o, x, y, z;
		scanf("%d%d", &o, &x);
		switch (o) {
		case 1:
			scanf("%d%d", &y, &z);
			while (tops[x] != tops[y]) {
#define swap_by(trigger)\
	do {\
		if (trigger[x] > trigger[y]) {\
			int t = x;\
			x = y;\
			y = t;\
		}\
	} while (0);
				swap_by(deps);
				seg_add(oseg, z, g2s[tops[y]], g2s[y], 1, n, p);
				y = mama[tops[y]];
			}
			swap_by(g2s);
			seg_add(oseg, z, g2s[x], g2s[y], 1, n, p);
			break;
		case 2:
			z = 0;
			scanf("%d", &y);
			while (tops[x] != tops[y]) {
				swap_by(deps);
				z = ((long long)z + seg_sum(oseg, g2s[tops[y]],
					g2s[y], 0ll, 1, n, p)) % p;
				y = mama[tops[y]];
			}
			swap_by(g2s);
			z = ((long long)z + seg_sum(
				oseg, g2s[x], g2s[y], 0ll, 1, n, p)) % p;
			printf("%d\n", z);
			break;
		case 3:
			scanf("%d", &z);
			seg_add(oseg, z, g2s[x], sl[x], 1, n, p);
			break;
		case 4:
			printf("%d\n", seg_sum(
					oseg, g2s[x], sl[x], 0ll, 1, n, p));
			break;
		}
	}
	return 0;
}