树链剖分
对于一棵确定的树，如果我们要维护它的子树信息，链上的信息，树剖再合适不过了
树剖，即对一棵树进行剖分，把点，边划分在不同的集合，来优化
先给出一些定义
重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点；
轻儿子：父亲节点中除了重儿子以外的儿子；
重边：父亲结点和重儿子连成的边；
轻边：父亲节点和轻儿子连成的边；
重链：由多条重边连接而成的路径；
轻链：由多条轻边连接而成的路径；
除了叶子节点外，每个节点都有且仅有一个重儿子，剩下的都是轻儿子
然后这棵树就被分成了轻重链交替的东西
为啥要这么分呢，为了保证复杂度丫
可以发现，从任意节点向根走，经过的轻边和重链的个数不超过(log(n))条
证明：
首先，任意轻儿子的子树大小都小于其父亲子树大小的一半
因此，每跳一个轻边， 子树大小至少会增加两倍以上，所以显然是(log(n))的
至于重链，都是一段一段的，重链-轻边-重链-轻边这样交替
因此，重链是不会超过轻边+1的，所以也是(log(n))的
证毕
树剖实际上就是用线段树来维护所有重链（注意，每个点属于且仅属于一条重链），所以总复杂度是```(O(nlog^2n))
首先，我们进行第一次dfs，处理出每个点的son（重儿子），dep（深度），fa（父亲）， siz（子树大小）
然后，进行第二次dfs，处理dfs序（注意，重链的dfs序连续，搜的时候先搜重儿子，再搜轻儿子），还有dfs到点的映射数组，还有top（所在重链的链顶（最浅的那个点））
然后以dfs序为关键字构建线段树，就完了
如果是子树查询，实际上可以发现，这样的dfs序子树内依然连续，所以可以(query(dfn[x], dfn[x] + siz[x] -1))
对于树链查询，我们让两个点一直跳重链，每次都查询答案，知道两个点在一条重链上为止，最后再把两个点之间的答案统计一下就行，而且这样还能求LCA
LCA啥都能求（倍增LCA，树剖LCA，LCT求LCA， 欧拉序求LCA。。。）
扯远了。。
$ color{#0066ff}{ 题目描述 }$
如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：
操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z
操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和
(color{#0066ff}{输入格式})
第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。
接下来一行包含N个非负整数，分别依次表示各个节点上初始的数值。
接下来N-1行每行包含两个整数x、y，表示点x和点y之间连有一条边（保证无环且连通）
接下来M行每行包含若干个正整数，每行表示一个操作，格式如下：
操作1： 1 x y z
操作2： 2 x y
操作3： 3 x z
操作4： 4 x
(color{#0066ff}{输出格式})
输出包含若干行，分别依次表示每个操作2或操作4所得的结果（对P取模）
(color{#0066ff}{输入样例})
5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3
(color{#0066ff}{输出样例})
2
21
(color{#0066ff}{数据范围与提示})
时空限制：1s，128M
数据规模：
对于30%的数据： (N leq 10, M leq 10)
对于70%的数据： (N leq {10}^3, M leq {10}^3)
对于100%的数据： $N leq {10}^5, M leq {10}^5 $
（ 其实，纯随机生成的树LCA+暴力是能过的，可是，你觉得可能是纯随机的么233 ）
样例说明：
树的结构如下：
各个操作如下：
故输出应依次为2、21(重要的事情说三遍：记得取模)
上代码吧
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int maxn = 1e5 + 10;
int n, m, rt, mod;
struct node {
node *ch[2];
int l, r;
LL val, tag;
node(int l = 0, int r = 0, LL val = 0, LL tag = 0): l(l), r(r), val(val), tag(tag) { ch[0] = ch[1] = NULL; }
int mid() { return (l + r) >> 1; }
void upd() { val = (ch[0]->val + ch[1]->val) % mod; }
void trn(LL v) { (tag += v) %= mod; }
}*root;
struct EDGE {
int to;
EDGE *nxt;
EDGE(int to = 0, EDGE *nxt = NULL): to(to), nxt(nxt) {}
};
EDGE *head[maxn];
int dfn[maxn], nfd[maxn], val[maxn], top[maxn], cnt;
int fa[maxn], dep[maxn], siz[maxn], son[maxn];
void add(int from, int to) { head[from] = new EDGE(to, head[from]); }
void build(node *&o, int l, int r) {
o = new node(l, r);
if(l == r) return (void)(o->val = val[nfd[l]]);
build(o->ch[0], l, o->mid());
build(o->ch[1], o->mid() + 1, r);
o->upd();
}
void add(node *o, int l, int r, LL v) {
(o->val += 1LL * (r - l + 1) * v % mod) %= mod; //标记永久化
if(l <= o->l && o->r <= r) return o->trn(v);
if(l <= o->mid()) add(o->ch[0], l, std::min(o->mid(), r), v);
if(r > o->mid()) add(o->ch[1], std::max(o->mid() + 1, l), r, v);
}
LL query(node *o, int l, int r, LL tag = 0) {
if(l <= o->l && o->r <= r) return (o->val + (1LL * (o->r - o->l + 1) * tag % mod)) % mod;
LL ans = 0;
if(l <= o->mid()) (ans += query(o->ch[0], l, r, (tag + o->tag) % mod)) %= mod;
if(r > o->mid()) (ans += query(o->ch[1], l, r, (tag + o->tag) % mod)) %= mod;
return ans;
}
void dfs1(int x, int f) {
dep[x] = dep[fa[x] = f] + (siz[x] = 1);
for(EDGE *i = head[x]; i; i = i->nxt) {
if(i->to == f) continue;
dfs1(i->to, x);
siz[x] += siz[i->to];
if(siz[i->to] > siz[son[x]]) son[x] = i->to;
}
}
void addpath(int x, int y, LL z) {
int fx = top[x], fy = top[y];
while(fx != fy) {
if(dep[fx] <= dep[fy]) std::swap(fx, fy), std::swap(x, y);
add(root, dfn[fx], dfn[x], z);
fx = top[x = fa[fx]];
}
if(dep[x] <= dep[y]) std::swap(x, y);
add(root, dfn[y], dfn[x], z);
}
LL querypath(int x, int y) {
int fx = top[x], fy = top[y];
LL ans = 0;
while(fx != fy) {
if(dep[fx] <= dep[fy]) std::swap(fx, fy), std::swap(x, y);
(ans += query(root, dfn[fx], dfn[x])) %= mod;
fx = top[x = fa[fx]];
}
if(dep[x] <= dep[y]) std::swap(x, y);
return (ans + query(root, dfn[y], dfn[x])) % mod;
}
void dfs2(int x, int t) {
top[nfd[dfn[x] = ++cnt] = x] = t;
if(son[x]) dfs2(son[x], t);
for(EDGE *i = head[x]; i; i = i->nxt)
if(!dfn[i->to]) dfs2(i->to, i->to);
}
int main() {
n = in(), m = in(), rt = in(), mod = in();
for(int i = 1; i <= n; i++) val[i] = in();
int p, x, y, z;
for(int i = 1; i < n; i++) x = in(), y = in(), add(x, y), add(y, x);
dfs1(rt, 0), dfs2(rt, rt), build(root, 1, n);
while(m --> 0) {
p = in();
if(p == 1) x = in(), y = in(), z = in(), addpath(x, y, z);
if(p == 2) x = in(), y = in(), printf("%lld
", querypath(x, y));
if(p == 3) x = in(), z = in(), add(root, dfn[x], dfn[x] + siz[x] - 1, z);
if(p == 4) x = in(), printf("%lld
", query(root, dfn[x], dfn[x] + siz[x] - 1));
}
return 0;
}
99行~~