树链剖分~知识

树链剖分

1.相关概念：

树链：即为树上的路径；
剖分：即将路径分为重链和轻链；
重儿子：siz[u]为v的子节点中siz值最大的，那么u就是v的重儿子。
轻儿子：v的其它子节点;
重边：点v与其重儿子的连边;
轻边：点v与其轻儿子的连边;
重链：由重边连成的路径;在重链上的节点数是最多的,根节点的每一棵子树都应该向下找出一条重链；
轻链：轻边
如图：重链为加粗的链，其他的都为轻边

2.树剖步骤：

(1).将树进行轻边与重链的划分：令size[u]为以u为根节点的节点个数，v为u的儿子中size值最大的节点，则(u,v)即为重边，其余边为轻边；
(2).两次dfs：
    1).dfs1维护以下几点：
        A、dep[u]:表示u的深度；从1开始
        B、fa[u]:u的父节点；从1开始
        C、son[u]:u的重儿子；初始化为0的；
        D、size[u]:以u为顶端节点的节点的个数；从下往上逐渐加上去
    2）dfs2 维护以下几点：（主要是将这棵树重新编号）
        A、top[u]：u的顶端节点；
        B、tid[u]:重新对这棵树编号后的号码；tid[u]=++clk;
        C、val1[tid[u]]:重新编号后对应的权值;val[clk]=val[u];
剖分完毕后，每条重链相当于一段区间，然后用数据结构去维护，把所有重链首尾相接，放到数据结构上，然后维护整体。
有以下可能：
    1)、查询区间最大值：
        如果要查询的u和v不在同一重链上，则先判断top[u]和top[v]的深度，在深度较深的那个重链上直接查询（tid[top[v]],tid[v]）区间的最大值后将v跳fa[top[v]]上，直到u，v在同一条重链上，再进行查询这条重链上的最大值；
    2)、区间求和：
         也是与区间求最大值差不多，若u与v不再同一重链上，则先判断top[u]和top[v]的深度，在深度较深的那个重链上直接求（tid[top[v]],tid[v]）区间的和后将v跳fa[top[v]]上，直到u，v在同一条重链上，再进行求这条重链上的和；
    3)、单点修改：
        当查到这个点时，将它的值改为新的num；按照线段树来~~

3.相关性质：

 (1)轻边(u,v)中，size(v)<=size(u/2)
 (2)从根到某一点的路径上，不超过logn条轻边和不超过logn条重路径。

有需要可以看这个题：树的统计Count