树链剖分
简介
树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。
具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息；
重边与轻边，重链与轻链
在将一棵树分成若干条链时，我们最好不要盲目的分；
有一种有效的分割方法就是，分成重链与轻链；
重链：连续的重边组成一条链；
轻链：连续的轻边组成一条链；
那么怎么判断重边和轻边呢？
我们定义
重子节点 ：表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点；
轻子节点 ：表示剩余的所有子结点；
那么重边和轻边就是
重边：重子节点与它父节点相连的一条边；
轻边：轻子节点与它父节点相连的一条边；
如图
代码实现
首先我们给出一些；
重要的数组
$f[x]$ 表示 $x$ 节点的父节点；
$son[x]$ 表示 $x$ 节点的重子节点；
$dep[x]$ 表示 $x$ 节点的深度；
$size[x]$ 表示 $x$ 节点的子树的节点个数；
$top[x]$ 表示 $x$ 节点所在这条链上的顶部节点；
$id[x]$ 表示 $x$ 节点的$DFN$序，也就是在线段树中的编号；
$aa[x]$ 表示 $x$ $DFN$序的节点权值；
那么
剖分代码
inline void dfs(ll x,ll fa)//找重子节点 { size[x]=1; f[x]=fa;//记录父节点 for(re ll i=head[x];i;i=e[i].stb) { ll xx=e[i].to; if(xx==fa)//不能遍历到父节点 continue; dep[xx]=dep[x]+1;//统计深度 dfs(xx,x); size[x]+=size[xx];//统计子树节点数 if(!son[x]||size[xx]>size[son[x]]) son[x]=xx;//找重子节点，也就是子树节点数最多的子节点 } } ll tot=0;//统计在线段树中的编号 inline void DFS(ll x,ll t)//t 表示这条链的顶部 { top[x]=t;//记录 id[x]=++tot;//记录在线段树中的编号 aa[tot]=w[x];//记录在线段树中的权值 if(!son[x])//如果没有重子节点 return;//返回 DFS(son[x],t);//先遍历重子节点 for(re ll i=head[x];i;i=e[i].stb) { ll xx=e[i].to; if(xx==f[x]||xx==son[x])//遍历轻子节点 continue; DFS(xx,xx);//每个开始的轻子节点的链顶就是自己 } }
调用代码
dfs(1,0); DFS(1,1);//1 所在链的顶部就是自己
求LCA
inline ll LCA(ll x,ll xx) { while(top[x]!=top[xx]) { if(dep[top[x]]>dep[top[xx]]) x=f[top[x]]; else xx=f[top[xx]]; } if(dep[x]<dep[xx]) return x; else return xx; }
线段树维护信息
更新中。。。