P3384 【模板】重链剖分 / 树链剖分
大意
支持树上的路径修改和路径查询，子树修改和子树查询。
思路
我们如果是对于线段上的这样的区间查询和修改，我们是可以用线段树来解决的，但是对于树上的问题呢？我们可以尝试将树上的节点映射到线段树上。
由于我们的 dfs 序在树上是段连续的区间，我们需要更好的分配，使得我们可以更好的维护树上的这些内容，一个朴素的想法就是把树划分为若干条链，使得为我们只需要分别维护这若干条链。
将树链化的过程叫做树剖，对于这样的路径的静态问题，我们一般采用 重链剖分，重链，即为重儿子所构成的链（重儿子即为 sz 最大的那个儿子），这样的话时间复杂度是有保证的。
于是我们可以两次 dfs 将树按重链剖分，将其映射到线段树上，如果要做询问或者是修改，就在不同的链上进行查询和修改。
代码
#include <iostream>
#include <vector>
#define int long long
#define lc u << 1
#define rc u << 1 | 1
using namespace std;const int MAXN = 1e5 + 5;
int dep[MAXN], fa[MAXN], sz[MAXN], son[MAXN];
int id[MAXN], top[MAXN], nw[MAXN], cnt = 0, x[MAXN];
vector<int> e[MAXN];
struct Tree{int l, r, sum, add;
}t[MAXN * 4];void pushup(int u){t[u].sum = t[lc].sum + t[rc].sum;
}void pushdown(int u){if(t[u].add){t[lc].sum += t[u].add * (t[lc].r - t[lc].l + 1);t[rc].sum += t[u].add * (t[rc].r - t[rc].l + 1);t[lc].add += t[u].add;t[rc].add += t[u].add;t[u].add = 0;}
}void build(int u, int l, int r){t[u] = {l, r, 0, 0};if(l == r){t[u].sum = nw[l];return;}int mid = (l + r) >> 1;build(lc, l, mid);build(rc, mid + 1, r);pushup(u);
}int query(int u, int l, int r){if(l <= t[u].l && t[u].r <= r){return t[u].sum;}pushdown(u);int mid = (t[u].l + t[u].r) >> 1;int ans = 0;if(l <= mid) ans += query(lc, l, r);if(r > mid) ans += query(rc, l, r);return ans;
}void change(int u, int l, int r, int k){if(l <= t[u].l && t[u].r <= r){t[u].add += k;t[u].sum += k * (t[u].r - t[u].l + 1);return;}pushdown(u);int mid = (t[u].l + t[u].r) >> 1;if(l <= mid) change(lc, l, r, k);if(r > mid) change(rc, l, r, k);pushup(u);
}int query_tree(int u){return query(1, id[u], id[u] + sz[u] - 1);
}void change_tree(int u, int k){change(1, id[u], id[u] + sz[u] - 1, k);
}int query_path(int u, int v){int ans = 0;while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]]) swap(u, v);ans += query(1, id[top[u]], id[u]);u = fa[top[u]];}if(dep[u] < dep[v]) swap(u, v);ans += query(1, id[v], id[u]);return ans;
}void change_path(int u, int v, int k){while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]]) swap(u, v);change(1, id[top[u]], id[u], k);u = fa[top[u]];}if(dep[u] < dep[v]) swap(u, v);change(1, id[v], id[u], k);
}void dfs1(int u, int f){fa[u] = f;dep[u] = dep[f] + 1;sz[u] = 1;for(int v : e[u]){if(v != f){dfs1(v, u);sz[u] += sz[v];if(sz[son[u]] < sz[v]) son[u] = v;}}
}void dfs2(int u, int tp){top[u] = tp;id[u] = ++cnt;nw[cnt] = x[u];if(!son[u]) return;dfs2(son[u], tp);for(int v : e[u]){if(v != fa[u] && v != son[u]){dfs2(v, v);}}
}signed main(){cin.tie(0) -> sync_with_stdio(0);int n, m, r, p;cin >> n >> m >> r >> p;for(int i = 1;i <= n;i ++){cin >> x[i];}for(int i = 1, u, v;i < n;i ++){cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}dfs1(r, 0);dfs2(r, r);build(1, 1, n);while(m--){int op, x, y, z;cin >> op;switch(op){case 1:cin >> x >> y >> z;change_path(x, y, z);break;case 2:cin >> x >> y;cout << query_path(x, y) % p << '\n';break;case 3:cin >> x >> z;change_tree(x, z);break;case 4:cin >> x;cout << query_tree(x) % p << '\n';break;}}return 0;
}