主要是根据学长的课件来透彻的.
所谓树链剖分，就是将树上的边进行划分。
树链剖分有重链剖分，长链剖分，实链剖分等等。
长链剖分是用来\(O(1)\)求\(k\)级祖先的，和优化一些树形DP，具体地来说是一些跟深度有关的DP。
实链剖分是我们常说的LCT(Link-Cut-Tree)。
本文介绍的就是重链剖分。
既然是重链剖分，那么一定有重链和轻链，但是我们怎么来划分轻重链呢？
我们定义：一个节点的所有子节点中\(size\)最大的那个节点为重儿子；那么这两个节点之间所连的边为一条重边。
这样的话我们会得到一些性质。
性质1：从根节点到叶子节点的路径上，跳重链的次数不会超过\(O(logn)\)，从叶子节点到根节点，也成立
证明：我们考虑，什么时候会跳重链，一定是当他需要向轻儿子走的时候废话。那么轻儿子的\(size\)，一定小于他父亲节点
的\(\frac{1}{2}\)，那么不断走轻儿子，一直乘\(\frac{1}{2}\)，只需要跳\(\log n\)次，就到\(1\)了，也就是叶子节点。
代码：
int fa[maxn], dep[maxn], size[maxn], height_son[maxn];
vector<int> v[maxn];
inline void add(int x, int y){return (void)(v[x].push_back(y));}
void bulid_poutree(int now){
size[now] = 1;
for(int i = 0; i < v[now].size(); i ++){
int to = v[now][i];
if(dep[to]) continue;
dep[to] = dep[now] + 1;//下一点的深度为当前点深度加一
fa[to] = now;
bulid_poutree(to);
size[now] += size[to];
if(size[to] > size[height_son[now]]) height_son[now] = to;//找到他的重儿子
}
}
我们考虑，如果两个点在同一条重链上，那么肯定是深度小的是LCA。
但是如果不在呢？
我们是不是可以像倍增一下跳（也仅仅是像），跳重链，向上跳，然后一直跳到两个点在同一条重链上，再像刚才一样处理。
让谁跳呢，深度大的？
不不不，是\(top\)深度大的跳。
因为，既然两个点不在同一条重链上，那么显然，他们的\(top\)，也不在同一条重链上。
那么类似于倍增，让\(top\)跳\(fa\)，直到跳到同一条重链上。
深度小的是LCA。
本人还不透彻，不如去写倍增
前置芝士：线段树。
先上一道例题来透彻一下树链剖分吧。
好像不只是跳重链那么简单。
在这里，我们引入一个叫做\(dfs\)序的概念。
\(dfs\)序：我们在遍历整棵树时，每个节点被遍历到的时间戳（即这个节点是第几个被遍历到的）。
那么我们显然可以发现一颗子树内的\(dfs\)序是连续的，而且一条链上的\(dfs\)序也是连续的。
那么我们在询问一条路径时，就可以把这条路径分成好几条链，我们对于每条链分别统计即可。
那么我们怎么才能维护每条链的信息呢？
注意：一条链上的\(dfs\)序是连续的，那么问题转化为，如何维护一个区间的信息？
当然是线段树啊。
什么区间和，区间最值，区间覆盖，线段树简直不能再合适了。
那么是不是这道题就做完了呢？
那么我就可以保证我们树链剖分的时间复杂度了\(O(n\log^2n)\)
int fa[maxn], dep[maxn], size[maxn], top[maxn], dfn[maxn], id[maxn], height_son[maxn];
/*其中dfn为该点所对应的dfs序，id为该点的dfs序所对应的自己原来的编号（不确定对不对qaq）），top为这条重链上最高的点（这个是对的qwq）*/
vector<int> v[maxn];
inline void add(int x, int y){return (void)(v[x].push_back(y));}
void bulid_poutree(int now){
size[now] = 1;
for(int i = 0; i < v[now].size(); i ++){
int to = v[now][i];
if(dep[to]) continue;
dep[to] = dep[now] + 1;//下一点的深度为当前点深度加一
fa[to] = now;
bulid_poutree(to);
size[now] += size[to];
if(size[to] > size[height_son[now]]) height_son[now] = to;//找到他的重儿子
}
}
void dfs(int now, int topfa){ //找到点对应的dfs序
top[now] = topfa;
dfn[now] = ++cnt;
id[cnt] = now;
if(height_son[now]) dfs(height_son[now], topfa); //先走重链
for(int i = 0; i < v[now].size(); i ++){//走轻链
int to = v[now][i];
if(fa[now] == to or height_son[now] == to) continue;
dfs(to,to);
}
}
找到dfs序以后我们就把这个问题美滋滋的转化为了区间问题
原文：https://www.cnblogs.com/Vanyun/p/13286973.html