树链剖分
树链剖分：通过轻重边剖分将树分割成多条链，然后利用数据结构来维护这些链
部分概念如下：
重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点；
轻儿子：父亲节点中除了重儿子以外的儿子；
重边：父亲结点和重儿子连成的边；
轻边：父亲节点和轻儿子连成的边；
重链：由多条重边连接而成的路径；
轻链：由多条轻边连接而成的路径；
变量阐释
| 名称 | 解释 |
|---|---|
| f[u] | 保存节点u的父亲节点 |
| d[u] | 保存节点u的深度值 |
| size[u] | 保存以节点u为根的子树节点个数 |
| son[u] | 保存重儿子 |
| rk[u] | 保存当前dfs标号在树中对应的节点 |
| top[u] | 保存节点u所在的链的头节点 |
| id[u] | 保存剖分后节点的新的编号（DFS执行的顺序） |
实现
1，对于一个点我们首先求出它所在的子树大小,找到它的重儿子（即处理出size,son数组）
例如：
若在一棵树中，节点1的叶子节点有2,3,4；
同时size[2]=5,size[3]=2,size[4]=6;
则节点1的重儿子是4;
注意：
如果一个点的多个儿子所在子树大小相等且最大，
那随便找一个当做它的重儿子就好了；
叶节点没有重儿子，非叶节点有且只有一个重儿子；
2，在dfs的过程中顺便记录该节点的父亲节点及深度
1,2可以在一遍dfs中完成void dfs1(int u,int fa,int depth) //当前节点、父节点、层次深度
{
f[u]=fa;
d[u]=depth;
size[u]=1; //这个点本身size=1
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==fa)
continue;
dfs1(v,u,depth+1); //层次深度+1
size[u]+=size[v]; //子节点的size已被处理，用它来更新父节点的size
if(size[v]>size[son[u]])
son[u]=v; //选取size最大的作为重儿子
}
}
//进入
dfs1(root,0,1);3,第二边dfs，然后连接重链，同时标记每一个节点的dfs序，为了用数据结构来维护链，我们保证重链上各个节点的编号连续。
void dfs2(int u,int t) //当前节点、重链顶端
{
top[u]=t;
id[u]=++cnt; //标记dfs序
rk[cnt]=u; //序号cnt对应节点u
if(!son[u])
return;
dfs2(son[u],t);
/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连 续，
一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v!=son[u]&&v!=f[u])
dfs2(v,v); //一个点位于轻链底端，那么它的top必然是它本身
}
}4，两边dfs就是树链剖分的主要处理，我们这时已经将一条重链上的dfs序连续，接下来，就需要用数据结构来维护重链上的信息。
最后，靠自己了，助推结束。。。。。。