树链剖分初识

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

前言

简单说两句

其实这个还真的不是太难理解，本蒟蒻就来简单说说这个算法。

正文

大概作用

就是将一个树形转化为线形，可以使用线段树、树状数组等各种数据结构加以维护。

基本概念

  1. 重结点：子树结点数目最多的结点
  2. 轻节点：父亲节点中除了重结点以外的结点
  3. 重边：父亲结点和重结点连成的边
  4. 轻边：父亲节点和轻节点连成的边
  5. 重链：由多条重边连接而成的路径
  6. 轻链：由多条轻边连接而成的路径

性质

  1. 如果(u, v)是一条轻边，那么size(v) <(=) size(u)/2
  2. 从根结点到任意结点的路所经过的轻重链的个数必定都小与O(logn)

代码

(个人码风有点不好，请见谅)
需要两次DFS

第一次DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int fa[maxn],son[maxn],siz[maxn],dep[maxn];
//fa[u]表示u的父节点,son[u]表示u的重儿子节点。
//siz[u]表示以u为根的子树的大小,dep[u]表示u在树中的深度。
//注意，一般博主习惯将根节点的深度初始为1
void dfs1(int u,int father){
	fa[u]=father,siz[x]=1;//记录u的父节点，siz[u]初始化
	for(int i=head[x];i;i=edge[i].nxt){
    //这里博主用的是前向星存边
		int v=edge[i].to;//u的子节点
		if(v!=father){
			dep[v]=dep[u]+1;//更新子节点的深度
			dfs1(v,u);//向下搜索
            //回溯时更新siz[u],和son[u]
			siz[u]+=siz[v];//这步就不说了
			if(siz[v]>siz[son[u]]) son[u]=v;
            //这里是更新重儿子节点,如果当前子节点v的子树size比当前保存
            //的son[u]的子树size还小的话就更新(初始时son[u]为0,size也为0)
		}
	}
}

第二次DFS

这是树剖的关键，也是树形转线形的重要部分(如果讲的不好请见谅)
这一步是将整个树分成若干条重链。每个节点标记一个dfs序，将树上的点变成一个序列中的编号，同样记录下这个编号对应的节点，我们还需要记录每一条重链的开端节点（具体为什么可以看看我那例题的文章）。
为什么这样，由于蒟蒻也讲不太清楚，所以就偷懒不说了，望见谅。
(就这样水了过来)

给出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int top[maxn],in[maxn],id[maxn],tot;
//个人码风奇丑无比，请不要在意数组名 
//top[u]表示u所在点重链 的开始节点
//in[u]表示这一个节点的dfs序,就是编号 
//id[u]表示u这一个编号对应的树的节点
void dfs2(int u,int tp){
    //tp表示当前重链的开始节点
	top[u]=tp,in[u]=++tot,id[tot]=u;
    //记录一下当前节点的top
	if(son[u]) dfs2(son[u],tp);//如果有重节点,就继续当前重链
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v!=fa[x]&&v!=son[x]) dfs2(v,v);
        //如果这点是轻点，以它自己为重链开始点，开始一条重链
	}
}

结束了。。。
(还有一些奇奇怪怪的复杂度证明等等请大家baidu才不说我不会呢！)

例题

下面如果还记得的话会更新一点例题：

  1. 月下“毛景树”
    待更新······