树链剖分
树链剖分常用于解决树上路径查询的问题。
原理:对于树上两点之间的路径 \(u\) -> \(v\),根据某种策略,将之拆分成若干条链,然后利用线段树等数据结构单独维护这些子链,最后将答案合并。
常用的剖分方法:轻重边划分。
剖分
树种的边可以分为两种边:重边和轻边。
设 \(size_u\) 表示以点 \(u\) 为根的子树的节点个数,令 \(v\) 表示 \(u\) 的儿子节点中 \(size\) 值最大的,则 \(v\) 是 \(u\) 的重儿子,边 \((u,v)\) 是一条重边,对于点 \(u\) 到其他儿子的边都为轻边。
如图所示。
性质及规定
1.如果边 \((u,v)\) 为轻边,则 \(size_v \le \frac{size_u}{2}\)
因为边 \((u,v)\) 若为轻边,则证明点 \(v\) 为点 \(u\) 的非重儿子,即 \(size_v\) 在点 \(u\) 的所有儿子的 \(size\) 值中非最大,则 \(size_v\) 最大只能占 \(size_u\) 的一半,若超过一半则点 \(v\) 会成为点 \(u\) 的重儿子。
例如上图中以点 \(2\) 为根的子树,\(size_5 = \frac{size_2}{2}\) 。
2.从根到某一点 \(v\) 的路径上,轻边个数不多于 \(logn\)
略。
3.称某条路径为重路径(重链),当且仅当它全部由重边组成,一个点也算一条重路径
略。
4.每个点都在且仅在一条重路径上
对于每条从点 \(u\) 发出的边中,只会有一条重边,因此扩展到整棵树上,每个点只会被一条重边经过。
代码实现
规定以下数组意义:
\(fa_x\) : 点 \(x\) 的父节点
\(dep_x\) : 点 \(x\) 在以点 \(1\) 为根时在树上的深度
\(size_x\) : 以点 \(x\) 为根的子树的节点个数(包括点 \(x\) 本身)
\(son_x\) : 点 \(x\) 的重儿子
\(top_x\) : 点 \(x\) 所在重链的顶部节点(即深度最小的节点)
\(seg_x\) : 点 \(x\) 在线段树上映射的最底层节点下标
\(rev_x\) : 线段树中最底层位置 \(x\) 所映射的树上的点
\(seg_x\) 与 \(rev_x\) 的关系为 \(rev_{seg_x}=x\)
以上七个数组可通过两次dfs求得,第一次dfs求出前四个,第二次dfs求出后三个。
void dfs1(int x,int p)//x点,其父节点为p
{
size[x]=1;
fa[x]=p;//求父节点
dep[x]=dep[p]+1;//求深度
for(int i=h[x];i;i=edge[i].next)
{
int y=edge[i].to;
if(y!=p)
{
dfs1(y,x);
size[x]+=size[y];//求子树大小
if(size[y]>size[son[x]])//更新重儿子
son[x]=y;
}
}
}
void dfs2(int x,int p)//x点,其父节点为p
{
if(son[x])//优先更新重节点
{
seg[son[x]]=++tot;//线段树映射
top[son[x]]=top[x];//重链顶节点传递
rev[tot]=son[x];//线段树反映射
dfs2(son[x],x);
}
{
for(int i=h[x];i;i=edge[i].next)
{
int y=edge[i].to;
if(!top[y])
{
seg[y]=++tot;
rev[tot]=y;
top[y]=y;//非重链节点自开一链
dfs2(y,x);
}
}
}
}
//主函数中
tot=1;
seg[1];
top[1]=1;
rev[1]=1;
dfs2(1,0)
查询实现
将一条路径 \((u,v)\) 剖分成若干条重路径的过程,实际上就是寻找最近公共祖先的过程。
假定 \(top_u\) 和 \(top_v\) 不同,那么他们的 LCA 可能在其中的一条重链上,也可能在其他的重链上。但 LCA 显然不在顶点深度较大的那条重链上,所以我们先处理顶点深度较大的那条重链。假设 \(top_u\) 较大,则可以直接跳到 \(fa_{top_u}\) 处,且跳过的这一段,在线段树中是一段区间,若我们按照深度从小到大来存储点,则这段区间为 \([seg_{top_u},seg_u]\) 。当点 \(u\) 和点 \(v\) 的顶点 \(top\) 相同时,说明它们走到了同一条重链上,这时他们之间的路径也是序列上的一段区间,且两者中深度较小的点是原路径的LCA。
代码
void ask(int x,int y)//路径 x->y,视情况选择是否返回答案(void\int\...)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
query(1,1,tot,seg[top[x]],seg[x]);
//(线段树顶点,当前区间左端,当前区间右端,目标区间左端,目标区间右端)
x=fa[top[x]];//保证dep[top[x]]>dep[top[y]]
}
if(dep[x]<dep[y])
swap(x,y);
query(1,1,tot,seg[y],seg[x]);
return;
}
总结
树链剖分本质上是通过轻重链区分的方式将一棵树分为若干条链,通过数据结构维护并求解,是分治思想的运用。
同时树链剖分支持单点修改操作,在原图、线段树上对应节点进行单点修改即可。
注:函数 \(query\) 实现方式与普通二分线段树无异
标签:剖分,int,top,树链,seg,son,节点,size From: https://www.cnblogs.com/AnEasySong/p/shu_lian_pou_fen.html