树链剖分，简称树剖。
它本质上就是把树划分成多条链，然后就可以使用线性数据结构如线段树等轻松维护树上路径的信息。
常见的剖分方法有重链剖分，长链剖分等。
一、重联剖分
最典型的一种剖分方式，看名字就知道其本质就是每次以子节点中子树最大的（称为重儿子）为链的剖分，我们称重链上的边叫重边，其他都叫轻边
这是一棵以1为根的树，那么其中重链就有1 2 4 6（或7）和3 8两条
从感性上理解，每次选重儿子作为链，任意路径经过的链不会太多，复杂度很优秀
从理性上分析，首先给出结论，任何一条路径最多被划分成\(log(n)\)条连续的链，证明：
每一次切换链，必然经过一条轻边（不妨记作u -> v），
由于它是轻边，所以v子树的大小至少是u子树大小的两倍，
而树的大小n是一定的，故最多划分为\(log_2(n)\)条连续的链
Q.E.D.
代码也是非常和蔼可亲
//树链剖分
/*
First: If you need, remember to use freopen and don't forgot init myfreopen.
Second: Remember to check int & ll, maybe the problem need ll or others.
*/
#include<bits/stdc++.h>
// simple name
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pque priority_queue
#define x1 x_1
#define y1 y_1
#define fir first
#define sec second
#define pb push_back
#define myfreopen freopen(".in", "r", stdin),freopen(".out", "w", stdout)
// function
#define ls(x) (x << 1)
#define rs(x) ((x << 1) | 1)
#define mid(l, r) ((l + r) >> 1)
#define debug(x) cerr << x << endl
#define dist(x, y, x2, y2) sqrt((x - x2) * (x - x2) + (y - y2) * (y - y2))
#define WA cerr << "Wrong Answer" << endl
#define init_inf32(x) memset(x, 0x3f3f3f3f, sizeof(x))
#define init_inf64(x) memset(x, 0x3f3f3f3f3f3f3f3fll, sizeof(x))
#define init_0(x) memset(x, 0, sizeof(x))
#define Dec(x) fixed << setprecision(x)
// val
#define eps 1e-9
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3fll
#define mod1 (int)(1e9 + 7)
#define mod2 998244353
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
mt19937 rnd(time(0) ^ clock());
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const int N = 1e5 + 5;
ll P;
ll n, m, rt;
vector<ll> vc[N];
ll val[N], f[N], siz[N], h[N], dfn[N], dep[N], son[N], tot;
namespace Seg_T{ll sum[N << 2], lazy[N << 2];inline void up(int x){sum[x] = (sum[ls(x)] + sum[rs(x)]) % P;}inline void down(int x, int l, int r){int mid = mid(l, r);if(lazy[x]){sum[ls(x)] = (sum[ls(x)] + lazy[x] * (mid - l + 1)) % P;sum[rs(x)] = (sum[rs(x)] + lazy[x] * (r - mid)) % P;lazy[ls(x)] = (lazy[ls(x)] + lazy[x]) % P;lazy[rs(x)] = (lazy[rs(x)] + lazy[x]) % P;lazy[x] = 0;}}inline void modify(int x, int l, int r, int ql, int qr, int v){if(ql <= l && qr >= r){sum[x] = ((r - l + 1) * v + sum[x]) % P;lazy[x] = (lazy[x] + v) % P;return ;}if(lazy[x]) down(x, l, r);int mid = mid(l, r);if(ql <= mid) modify(ls(x), l, mid, ql, qr, v);if(mid < qr) modify(rs(x), mid + 1, r, ql, qr, v);up(x);}inline ll query(int x, int l, int r, int ql, int qr){if(ql <= l && qr >= r) return sum[x];down(x, l, r);int mid = mid(l, r);ll ret = 0;if(ql <= mid) ret = query(ls(x), l, mid, ql, qr);if(mid < qr) ret = (ret + query(rs(x), mid + 1, r, ql, qr)) % P;return ret;}
}
using namespace Seg_T;
namespace Init{inline void dfs(int x, int fa){f[x] = fa; siz[x] = 1;dep[x] = dep[fa] + 1;for(int y : vc[x]){if(y == fa) continue;dfs(y,x);siz[x] += siz[y];if(siz[son[x]] < siz[y]) son[x] = y;}}inline void dfs1(int x, int t){dfn[x] = ++tot;h[x] = t;modify(1, 1, n, dfn[x], dfn[x], val[x]);if(son[x] == 0) return ;dfs1(son[x], t);for(int y : vc[x]){if(y == f[x] || y == son[x]) continue;dfs1(y, y);}}
}
namespace Operate{inline void path_modify(int u, int v, ll val){while(h[u] != h[v]){if(dep[h[u]] < dep[h[v]]) swap(u, v);modify(1, 1, n, dfn[h[u]], dfn[u], val);u = f[h[u]];}if(dep[u] > dep[v]) swap(u, v);modify(1, 1, n, dfn[u], dfn[v], val);}inline ll path_query(int u, int v){ll ret = 0;while(h[u] != h[v]){if(dep[h[u]] < dep[h[v]]) swap(u, v);ret = (ret + query(1, 1, n, dfn[h[u]], dfn[u])) % P;u = f[h[u]];}if(dep[u] > dep[v]) swap(u, v);ret = (ret + query(1, 1, n, dfn[u], dfn[v])) % P;return ret;}inline void subtree_modify(int x, ll val){modify(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, val);}inline ll subtree_query(int x){return query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1);}
}
using namespace Init;
using namespace Operate;inline void init(){cin >> n >> m >> rt >> P;for(int i = 1; i <= n; i++) cin >> val[i];for(int i = 1; i < n; i++){int u, v; cin >> u >> v;vc[u].push_back(v);vc[v].push_back(u);}
}
inline void solve(){dfs(rt, 0);dfs1(rt, 0);while(m--){int op, x, y, z;cin >> op;if(op == 1){cin >> x >> y >> z;path_modify(x, y, z);}else if(op == 2){cin >> x >> y;cout << path_query(x, y) << "\n";}else if(op == 3){cin >> x >> z;subtree_modify(x, z);}else{cin >> x;cout << subtree_query(x) << "\n";}}
}signed main(){//myfreopen;ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);init();int T = 1;// cin >> T;while(T--){solve();}return 0;
}
代码来源：Luogu P3384【模板】树链剖分