树链剖分

时间：2019-08-03 19:22:51 阅读：93 评论：0 收藏：0 [点我收藏+]

技术分享图片

前言：

　　首先，在学树链剖分之前最好先把 LCA、树形DP、DFS序这三个知识点学了
　　emm还有必备的链式前向星、线段树也要先学了。

　　如果这三个知识点没掌握好的话，树链剖分难以理解也是当然的。

一、简介

　　树链剖分就是对一棵树分成几条链，把树形变为线性，减少处理难度

　　需要处理的问题：

- 　将树从x到y结点最短路径上所有节点的值都加上z
- 　求树从x到y结点最短路径上所有节点的值之和
- 　将以x为根节点的子树内所有节点值都加上z
- 　求以x为根节点的子树内所有节点值之和

　　概念

- 重儿子：对于每一个非叶子节点，它的儿子中以那个儿子为根的子树节点数最大的儿子为该节点的重儿子 (Ps: 感谢@shzr大佬指出我此句话的表达不严谨qwq, 已修改)
- 轻儿子：对于每一个非叶子节点，它的儿子中非重儿子的剩下所有儿子即为轻儿子
- 叶子节点没有重儿子也没有轻儿子（因为它没有儿子。。）
- 重边：一个父亲连接他的重儿子的边称为重边 //原写法：连接任意两个重儿子的边叫做重边
- 轻边：剩下的即为轻边
- 重链：相邻重边连起来的连接一条重儿子的链叫重链
  - 对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为1的链
  - 每一条重链以轻儿子为起点

　　性质

　　　　如果边(u,v)为轻边，那么，size（u）>=size(v)*2

　　　　根到某一节点经过的路径中轻边的数量一定不多于log（n）

　　　　根到某一节点经过的路径中重链的数量一定不多于log（n）

二、算法流程

　　dfs1()

　　　　这个dfs1要处理几件事情：

标记每个点的深度deep[]
标记每个点的父亲fa[]
标记每个非叶子节点的子树大小(含它自己)
标记每个非叶子节点的重儿子编号w_son[]

inline void Dfs1(int u,int father,int fdeep)
{
    deep[u]=fdeep,fa[u]=father,root_size[u]=1;//标记节点的父亲，深度，当前以u为树根的树中的节点个数 
    int pw_son=-1;//先设重儿子的root_size为-1 
    for(int i=head[u];i;i=edge[i].next)
    {
        if(edge[i].to==father) continue;//无向图"返祖边"不需要 
        Dfs1(edge[i].to,u,fdeep+1);//搜索儿子节点 
        if(root_size[edge[i].to]>pw_son) w_son[u]=edge[i].to;    
        root_size[u]+=root_size[edge[i].to];//更新重儿子 
    }
}

　　dfs2()

　　　　这个dfs2也要预处理几件事情

标记每个点的新编号id
赋值每个点的初始值到新编号上
处理每个点所在链的顶端
处理每条链

inline void Dfs2(int u,int ftop)
{
    top[u]=ftop;//将u加入链头为ftop的链中 
    id[u]=++cnt;//记录每一个节点的时间戳 
    w[cnt]=a[u];//按照时间戳加入权值
    if(!son[u]) return;//没有儿子，直接返回 
    Dfs2(son[u],ftop);//先深搜重儿子，这样就会保证重儿子的序列尽可能的小 
    for(int i=haed[u];i;i=edge[i].next)
        if(edge[i].to!=u&&edge[i].to!=son[u])
            Dfs2(edge[i].to,edge[i].to)//生成一条以edge[i].to为链头的新链 
}