首页 > 其他分享 >树链剖分

树链剖分

时间:2023-10-12 19:56:14浏览次数:33  
标签:剖分 int top 树链 seg son 节点 size

树链剖分

树链剖分常用于解决树上路径查询的问题。

原理:对于树上两点之间的路径 \(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

相关文章

  • 算法:树链剖分
    去年就看过树链剖分的视频了,当时连树状数组,线段树都没学,对树的dfs也一知半解,所以基本完全听不懂。昨天又重新看了一般,感觉思路挺简单,应该比线段树简单吧,从用树链剖分求LCA来看确实是这样的,但是没有想到的是用线段树维护树链剖分。QAQ这应该是我打过最长的代码吧!(3K)树链剖分......
  • 浅谈树链剖分—轻重链剖分
    闲话似乎会有很多种树剖,什么长链剖分之类的,但是暂时只会轻重链剖分(可怜)。以前的版本在这里,但是感觉写的太粗糙了,所以决定重写一篇(我也不知道为什么要一直写树剖而不写点别的)。正文引入如果给出一个序列,有一些区间修改查询之类的操作,直接上线段树什么的就完事了,但是如果给出的......
  • 树链剖分
    前言:本人太弱了,看着题解调了一下午,才A了树剖的板子题,所以写篇博客纪念一下(其实是怕自己忘了树剖怎么做)。本文以板子题为例子定义:树链剖分,计算机术语,指一种对树进行划分的算法,它先通过轻重边剖分将树分为多条链,保证每个于且只属于一条链,然后再通过数据结构(树状数组、BST、SPL......
  • [学习笔记] 树链剖分
    叫复习笔记或许更好。树链剖分就是把树剖成链去解决一些问题。定义重子节点:子节点中子树大小最大的节点。轻子节点:除重子节点外的其他子节点。重边:到重子节点的边。轻边:到轻子节点的边。记号\(dfn[x]\):DFS序,也是在线段树中的编号。\(son[x]\):重子节点。\(dep[x]\)......
  • 「学习笔记」树链剖分
    树链剖分用于将树分割成若干条链的形式,以维护树上路径的信息。具体来说,将整棵树剖分为若干条链,使它组合成线性结构,然后用其他的数据结构维护信息。树链剖分有很多种形式,本文要讲的是其中的轻重链剖分。树链剖分本质上就是把链从树上砍下来,然后放到树状数组或线段树上来维护。......
  • 长链剖分
    例题:P5903【模板】树上k级祖先题目描述思路长链剖分模板题。长链剖分:计算\(f[i][j]\)表示\(i\)的\(2^j\)级祖先;计算\(up[i][j]\)表示\(i\)的\(j\)级祖先;计算\(down[i][j]\)表示在长链上从\(i\)向下走\(j\)步到达的祖先。计算\(i\)的\(k\)级祖......
  • 树链剖分学习(复习?)笔记
    树链剖分,即树剖。顾名思义,树链剖分就是将一棵树通过某种方式剖分成若干条链,再利用\(dfs\)序,从而将树上的问题转化为序列上的问题。树剖的方式有不止一种,比如重链剖分、长链剖分。最常用的(大概?)是重链剖分。此处介绍重链剖分。首先,我们定义一个节点的重儿子为此节点的所有儿......
  • 树链剖分/重链剖分模板
    #include<bits/stdc++.h>usingnamespacestd;intn,m,d,mod,w[200005],wt[200005],e[200005],ne[200005],h[200005],idx=1,t[800005],l[800005],r[800005],tag[800005];intson[200005],id[200005],fa[200005],cnt,dep[200005],siz[200005],top[200005];/*son[]重儿子......
  • 『复习笔记』树链剖分(重链剖分)
    前言(事出必有因)今天模拟赛有一道线段树+LCA的题,考场上码了两个小时,结果pushup错了,结果线段树调完了,发现TLE了,原来是求LCA炸了。。因为我用的倍增(我就是倍增狗你能把我怎么样),但是倍增的一个重要问题就是log都跑满了,但是树剖跑不满log,别问我为什么不用Tarjan,因为这题是在线的不好......
  • 树链剖分 | 洛谷 P4114 Qtree1
    前言题目链接:洛谷P4114Qtree1前置知识:树链剖分题意给定一棵树,有修改边权和查询两点之间边权最大值两种操作,对于每个查询输出结果。解析已经在前置博客里提到,树链剖分可以将树上的任意一条路径划分成不超过\(O(\logn)\)条连续的链,保证划分出的每条链上的节点DFS序......