今天又是和树互砍的一天呢，这玩意我明天必然得复习一遍，修到最后自己都不知道是怎么过的，还用了大佬的板子。
#include <bits/stdc++.h> using namespace std; //#define int long long #define lson rt << 1 #define rson rt << 1 | 1 typedef long long ll; typedef pair<int, int> pii; typedef pair<long long, long long> PII; const int maxn = 2e5 + 10; int n, m, r, mod; int head[maxn], tot; struct edge { int to, next; } edge[maxn]; int w[maxn], wt[maxn]; //w输入时的权值，wt编号后的权值 int son[maxn], id[maxn], fa[maxn], dep[maxn], sz[maxn], top[maxn], cnt = 0; //son重儿子、id新编号、fa父亲节点、dep深度、sz子树大小、top顶端、cnt标号。 void add(int u, int v) { edge[++tot].to = v; edge[tot].next = head[u]; head[u] = tot; } struct SegTree { int tree[maxn << 2], lazy[maxn << 2]; void push_down(int rt, int len) { if (lazy[rt]) { lazy[lson] += lazy[rt]; lazy[rson] += lazy[rt]; tree[lson] += lazy[rt] * (len - len / 2); tree[rson] += lazy[rt] * (len / 2); tree[lson] %= mod; tree[rson] %= mod; lazy[rt] = 0; } } void build(int rt, int l, int r) { if (l == r) { tree[rt] = wt[l]; tree[rt] %= mod; return; } int mid = (l + r) >> 1; build(lson, l, mid); build(rson, mid + 1, r); tree[rt] = (tree[lson] + tree[rson]) % mod; } int query(int rt, int l, int r, int L, int R) { if (L <= l && r <= R) { return tree[rt]; } push_down(rt, r - l + 1); int mid = (l + r) >> 1, res = 0; if (L <= mid) res = (res + query(lson, l, mid, L, R)) % mod; if (R > mid) res = (res + query(rson, mid + 1, r, L, R)) % mod; return res; } void update(int rt, int l, int r, int L, int R, int k) { if (L <= l && r <= R) { lazy[rt] += k; tree[rt] += k * (r - l + 1); return; } push_down(rt, r - l + 1); int mid = (l + r) >> 1; if (L <= mid) update(lson, l, mid, L, R, k); if (R > mid) update(rson, mid + 1, r, L, R, k); tree[rt] = (tree[lson] + tree[rson]) % mod; } } s_t; int query(int x, int y) { int res = 0; while (top[x] != top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); res += s_t.query(1, 1, n, id[top[x]], id[x]); res %= mod; x = fa[top[x]]; } if (dep[x] > dep[y]) swap(x, y); res += s_t.query(1, 1, n, id[x], id[y]); res %= mod; return res; } void update(int x, int y, int k) { while (top[x] != top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); s_t.update(1, 1, n, id[top[x]], id[x], k); x = fa[top[x]]; } if (dep[x] > dep[y]) swap(x, y); s_t.update(1, 1, n, id[x], id[y], k); } int query_son(int x) { int res = 0; res += s_t.query(1, 1, n, id[x], id[x] + sz[x] - 1); res %= mod; return res; } void update_son(int x, int k) { s_t.update(1, 1, n, id[x], id[x] + sz[x] - 1, k); } void dfs1(int u, int father) { dep[u] = dep[father] + 1; sz[u] = 1; fa[u] = father; int maxson = -1; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if (v == father) continue; dfs1(v, u); sz[u] += sz[v]; if (sz[v] > maxson) son[u] = v, maxson = sz[v]; } } void dfs2(int u, int topf) { id[u] = ++cnt; wt[cnt] = w[u]; top[u] = topf; if (!son[u]) return; dfs2(son[u], topf); for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if (v == fa[u] || v == son[u]) continue; dfs2(v, v); } } int main() { scanf("%d%d%d%d", &n, &m, &r, &mod); for (int i = 1; i <= n; ++i) scanf("%d", &w[i]); for (int i = 1; i < n; ++i) { int x, y; scanf("%d%d", &x, &y); add(x, y); add(y, x); } dfs1(r, 0); dfs2(r, r); s_t.build(1, 1, n); while (m--) { int k, x, y, z; scanf("%d", &k); if (k == 1) { scanf("%d%d%d", &x, &y, &z); update(x, y, z); } else if (k == 2) { scanf("%d%d", &x, &y); printf("%d\n", query(x, y)); } else if (k == 3) { scanf("%d%d", &x, &y); update_son(x, y); } else { scanf("%d", &x); printf("%d\n", query_son(x)); } } }