树链剖分的学习理解
【前言】
本文仅为本人学习树链剖分的理解和总结,有误之处请大佬指点迷津。也有与其他博客不同或矛盾之处。
【树链剖分】
顾名思义,将树结构,剖分成链状结构,然后将一条条的链拼接成线性结构,然后就可以通过线段树、树状数组等维护了。
说白了就是在树上,有些值不好维护,通过树链剖分转化成一个序列,而序列就好维护了。
树链剖分做的事情就是把树映射成一个序列,让线段树去维护这个序列,以达到维护树的目的。
【剖分方法】
1.概念
重儿子:结点u的子结点中,拥有最大子树的那个儿子结点。
轻儿子:除了唯一的重儿子,其余都为轻儿子
重链: 从结点u向重儿子延伸下去,所形成的一条链
轻链: 去掉重链,剩下的那些链都是轻链,一般来说,轻链都是孤立的点。
图中粗边连接的链就是重链,其余为轻链。标记红点的点为重链的起点。边上的数字表示dfs时的顺序(一定要重链的dfs序连续)。
2.设置数组
数组名 | 功能 |
dep[u] | 树上结点u的深度(根结点为0) |
dad[u] | 树上结点u的父结点(假设根结点为本身) |
siz[u] | 树上结点u的子树结点数目(包括u本身) |
son[u] | 树上结点u的重儿子 |
top[u] | 树上结点u的重链队长,即u所在的重链以top[u]为起点 |
rk[u] | 树上结点u对应的序列位置下标 |
id[ i ] |
序列上位置 i 对应的树上结点编号(基本无实际用处) |
3.求出2中的所有数组
两次dfs,第一次dfs,求出dep,dad,siz,son,这四个很简单。第二次dfs求top,rk,id,这里需要注意dfs优先进入重儿子。
其实rk数组才是主角,我们按照dfs进行的顺序,给树上点编号,并且让重链的编号都是连续的(dfs2优先进入重儿子的原因),这样我们就能用线段树维护这段重链了。
/************ 树链剖分 **************/
int dep[MAX],dad[MAX],siz[MAX],son[MAX];
int top[MAX],rk[MAX],id[MAX];
void dfs1(int u,int pre)
{
siz[u]=1; //u本身
son[u]=-1;
int maxsiz=0; //最大的儿子子树大小
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].t;
if(v==pre)continue;
dep[v]=dep[u]+1;
dad[v]=u;
dfs1(v,u); //注意dfs的位置
siz[u]+=siz[v];
if(maxsiz<siz[v])
{
maxsiz=siz[v];
son[u]=v;
}
}
}
void dfs2(int u,int fat,int &tag) //结点u,重链顶端
{
top[u]=fat;
rk[u]=++tag; //时间戳
id[tag]=u; //tag对应在树上的结点号
if(son[u]==-1)return; //没有孩子
dfs2(son[u],fat,tag); //优先重链dfs
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].t;
if(v==dad[u]||v==son[u])continue;
dfs2(v,v,tag);
}
}
void cuttree(int root) //将root为根的树链剖分
{
int tag=0;
dep[root]=0; //根的深度和父结点做一个初始化
dad[root]=root; //这是一个假设,根的父结点还是根
dfs1(root,root);
dfs2(root,root,tag);
}
4.修改操作
如果我们想对树上u-v之间的所有点的权值增加num,那么uv之间一定可以越过一些重链互相到达,那我们可以同LCA的思想处理。更新u-v,等同于更新u-v之间涉及到的重链,也就是线段树维护的一些区间。
void modify(int u,int v,ll num, int limit) //修改
{
int fu=top[u],fv=top[v];
while(fu!=fv) //uv不在同一条链上
{
if(dep[fu]>=dep[fv]) //u的深度大
{
update(rk[fu],rk[u],num,1,1,limit); //线段树更新这段区间
u=dad[fu]; fu=top[u];
}
else
{
update(rk[fv],rk[v],num,1,1,limit);
v=dad[fv]; fv=top[v];
}
} //循环结束时,fu-fv在同一链
if(dep[u]>dep[v])swap(u,v);
update(rk[u],rk[v],num,1,1,limit);
}
【练习题】
HDU3966 http://acm.hdu.edu.cn/showproblem.php?pid=3966
题解:https://blog.csdn.net/winter2121/article/details/81592775