洛谷 P3384 【模板】树链剖分
此博文只用来记录写树剖时我的错误（我写的真是太好看了！）
(ps)：因为(lfd)，我爱上了压行
(1.)不要混淆变量名、函数名，因为这个(WA)过(比如在(dfs1)里调用了(dfs2)……)
(2.)题目让你取模就不要忘记取模，第一次交只有部分取模了导致只有(30)分，而且要随时取模，随时取模， 随时取模！
(3.)全局变量初始值为(0)，但局部变量并不是！！在线段树的(asksum)部分我没给(ans)赋初值，查错查了很久
(4.)跳的时候是跳到链顶的父亲节点那里！不是跳到链顶！
(5.)查询或修改树上两个点之间路径的时候是查询点之间的，所以一开始不需要用(dfn[x]),(dfn[y])，而查询或者修改一个子树的权值时，就要用到(dfn[x])了，因为在第一遍(dfs)(我代码里的(prepare))之后，第二遍(dfs)就能够保证一棵子树的(dfn)序是连续的，所以可以直接用(dfn[x])和(dfn[x] + siz[x] - 1)来修改和查询这棵子树的权值和（因为自己也是自己子树的一员，所以要减一）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 1e6 + 11;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
int n, m, root, mod, w[A], pre[A];
struct node { int to, nxt; } e[A];
int head[A], cnt;
inline void add_edge(int from, int to) {
e[++cnt].to = to;
e[cnt].nxt = head[from];
head[from] = cnt;
}
namespace Seg {
#define lson rt << 1
#define rson rt << 1 | 1
struct tree { int l, r, w, lazy; } t[A];
inline void pushup(int rt) { t[rt].w = (t[lson].w + t[rson].w) % mod; }
inline void pushdown(int rt) {
t[lson].lazy = (t[lson].lazy + t[rt].lazy) % mod;
t[rson].lazy = (t[rson].lazy + t[rt].lazy) % mod;
t[lson].w += (t[lson].r - t[lson].l + 1) * t[rt].lazy; t[lson].w %= mod;
t[rson].w += (t[rson].r - t[rson].l + 1) * t[rt].lazy; t[rson].w %= mod;
t[rt].lazy = 0; return;
}
void build(int rt, int l, int r) {
t[rt].l = l, t[rt].r = r;
if(l == r) { t[rt].w = w[pre[l]] % mod; return; }
int mid = (l + r) >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
pushup(rt); return;
}
void update(int rt, int l, int r, int val) {
if(l <= t[rt].l && t[rt].r <= r) {
t[rt].lazy += val % mod; t[rt].lazy %= mod;
t[rt].w += (t[rt].r - t[rt].l + 1) * val % mod; t[rt].w %= mod;
return;
}
if(t[rt].lazy) pushdown(rt);
int mid = (t[rt].l + t[rt].r) >> 1;
if(l <= mid) update(lson, l, r, val);
if(r > mid) update(rson, l, r, val);
pushup(rt); return;
}
int asksum(int rt, int l, int r) {
if(l <= t[rt].l && t[rt].r <= r) { return t[rt].w % mod; }
if(t[rt].lazy) pushdown(rt);
int mid = (t[rt].l + t[rt].r) >> 1, ans = 0;
if(l <= mid) ans += asksum(lson, l, r);
if(r > mid) ans += asksum(rson, l, r);
return ans;
}
}
int dfn[A], top[A], siz[A], son[A], fa[A], tot, dep[A];
void prepare(int now, int fr) {
siz[now] = 1, fa[now] = fr, dep[now] = dep[fr] + 1;
for(int i = head[now]; i; i = e[i].nxt) {
int to = e[i].to;
if(to == fr) continue;
prepare(to, now); siz[now] += siz[to];
if(siz[to] > siz[son[now]]) son[now] = to;
}
}
void dfs(int now, int tp) {
dfn[now] = ++tot, pre[tot] = now, top[now] = tp;
if(son[now]) dfs(son[now], tp);
for(int i = head[now]; i; i = e[i].nxt) {
int to = e[i].to;
if(to == son[now] || to == fa[now]) continue;
dfs(to, to);
}
}
void update(int x, int y, int val) {
while(top[x] != top[y]) {
if(dfn[top[x]] < dfn[top[y]]) swap(x, y);
Seg::update(1, dfn[top[x]], dfn[x], val);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
Seg::update(1, dfn[x], dfn[y], val);
return;
}
int ask(int x, int y) {
int ans = 0;
while(top[x] != top[y]) {
if(dfn[top[x]] < dfn[top[y]]) swap(x, y);
ans += Seg::asksum(1, dfn[top[x]], dfn[x]), ans %= mod;
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
ans += Seg::asksum(1, dfn[x], dfn[y]), ans %= mod;
return (ans % mod + mod) % mod;
}
int main() {
n = read(), m = read(), root = read(), mod = read();
for(int i = 1; i <= n; i++) w[i] = read() % mod;
for(int i = 1; i < n; i++) {
int x = read(), y = read();
add_edge(x, y), add_edge(y, x);
}
prepare(root, 0);
dfs(root, root);
Seg::build(1, 1, n);
int opt, x, y, z;
while(m--) {
opt = read();
if(opt == 1) x = read(), y = read(), z = read() % mod, update(x, y, z);
if(opt == 2) x = read(), y = read(), cout << ask(x, y) % mod << '
';
if(opt == 3) x = read(), z = read(), Seg::update(1, dfn[x], dfn[x] + siz[x] - 1, z);
if(opt == 4) x = read(), cout << Seg::asksum(1, dfn[x], dfn[x] + siz[x] - 1) % mod << '
';
}
}