时间会冲淡痛苦的回忆，只有美好的事情才会永存。——《前进吧！登山少女》

树链剖分

你看这个树它像不像一座山一样

你能不能换个题目，这个题目太阴间了。——龙潜月十五

树链剖分是把一棵树分割成若干条链，以便于维护信息的一种方法，其中最常用的是轻重链剖分（Heavy - Light Path Decomposition），如果平时没有特别说明，树链剖分一般都指重链剖分。

重链剖分

定义

重子节点：其子节点中子树最大的子节点，如果有多个子树最大的子节点，取其一，如果没有子节点，就无重子节点。

轻子节点：只要不是重子节点，就是轻子节点。

重边：一个节点连向其重子节点的边。

轻边：一个节点连向其轻子节点的边。

我，一棵被重链剖分的树

如果把根节点看做轻的，那么从每个轻节点出发，不断向下走重边，都对应了一条链，于是我们把树剖分成了 条链。其中 是轻节点的个数。

重链剖分有一个重要的性质，对于节点数为 的树，从任意节点向上走到根节点，经过的轻边数量不超过 。这是因为，如果一个节点连向父节点的边是轻边，就必然存在子树不小于它的兄弟节点，那么父节点对应子树的大小一定超过该节点的两倍。每经过一条轻边，子树大小就翻倍，所以最多只能经过 条。

重链剖分的食用

基本剖分

我们通过两次 来进行重链剖分。第一趟 ，先得到每个节点的父节点 ，子树大小 ，深度 ，重子节点 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs1 (int p, int d) // 传入当前节点和当前深度  
{
	int size = 1, ma = 0; // size 存每个子树的大小，ma 存每个最大的子树里节点的数量  
	dep[p] = d;
	for (auto q : edge[p]) // 前向星遍历 
		if (!dep[p]) // 如果还未访问过
		{
			dfs1 (q, d + 1); // 传入子节点（终点）和深度 + 1
			fa[q] = p; // 设 q 的父节点为 p; 
			size += sz[q]; // 这个节点下面所有子树的大小的和就是这个节点代表子树的大小 
			if (sz[q] > ma) // 如果这个子节点代表的子树大小较大  
				hson[p] = q, ma = sz[q]; // 这个父节点的重子节点设为 q ， 更新最大的子树里节点的数量  
		}
	sz[p] = size; // 在前向星遍历结束后，将所得的子树大小全部加给这个值  
}

第二趟 ，得到每个节点的链头 ，即所在重链中深度最小的那个节点，根节点的链头是自己。

注意，这里如果把根节点看做是轻节点，那么所有重链的链头都是轻节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
top[root] = root; // 根节点的链头初始化为自身 
void dfs2 (int p) // 传入当前编号 
{
	for (auto q : edge[p]) // 前向星遍历 
	{
		if (!top[q]) // 如果这条链的链头还未被找到  
		{
			if (q == hson[p]) // 如果当前遍历到的节点就是 p 的重子节点 
				top[q] = top[p]; // 重子节点的链头是最上面的轻子节点 
			// 因为如果上面是个重子节点，我们已经遍历过它了，它的 top 就是一个轻子节点，链头会继承下来
			else
				top[q] = q;	// 轻子节点的链头就是自己  
		}
	} 
}

求最近公共祖先

树链剖分可以单次 地求最近公共祖先，且常数较小。假如要求两个节点的 ，如果它们在同一条链上，那直接输出深度较小的一个点就可以了。

A和B的祖先就是B

我们可以直接把链头深度较大的节点用其链头的父节点代替，然后继续求它与另一者的 。

整条链的跳跃

由于在链上可以 地跳转，每条链间由轻边连接，而经过轻边的次数又不超过 次，所以我们实现了 的 查询。

1
2
3
4
5
6
7
8
9
10
11
12
int LCA (int a, int b)
{
	while (top[a] != top[b]) // 如果两个点的链头不相同
	{
		if (dep[top[a]] > dep[top[b]]) // a 的链头的深度比 b 的链头的深度深 
			a = fa[top[a]]; // 将指针移动到 a 的链头的父节点 
		else
			b = fa[top[b]]; // 将指针移动到 b 的链头的父节点 
		// 等于是直接移动到另一条链上了 
	}
	return (dep[a] > dep[b] ? b : a); // 等到两者位于同一条链上时，比较深度 
}

结合数据结构

在进行了树链剖分之后，我们便可以配合线段树等数据结构维护树上信息，这需要我们改一下第二次 的代码，我们用 数组记录每个点的 序，用 数组记录每棵子树的最大 序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs2 (int p) // 传入编号 
{
	madfsn[p] = dfsn[p] = ++ cnt; // 扫到这个点先给它一个接下来的编号，而且每个最大的 dfs 序必在叶节点上  
	if (hson[p]) // 如果这个点存在重子节点 
	{
		// 这里用 hson[p] 来表示上面的 q ，也就是 p 的重子节点 
		top[hson[p]] = top[p]; // 重子节点的链头等于最上面的轻子节点
		// 与上面的 top[q] = top[p] 等价 
		dfs2 (hson[p]); // 将这个重子节点向下递归  
		madfsn[p] = max (madfsn[p], madfsn[hson[p]]); // 更新最大 dfs 序 
	}
	for (auto q : edge[p]) // 前向星遍历 
		if (!top[q]) // 如果这个点还没有链头（不用担心被覆盖，因为上面每个重子节点的链头已经找到过了  
		{
			top[q] = q; // 我们上面已经处理过重子节点的情况了，这里只需要处理轻子节点就可以  
			dfs2 (q); // 对边的终点进行向下递归  
			madfsn[p] = max (madfsn[p], madfsn[q]); // 因为存在别的子树，所以这个父节点的最大 dfs 序需更新。 
		}
}

这段代码也太阴间了吧，别祸害其他人，第一个这么写的人也是牛的。——龙潜月十五、nottttttthy

所以给出两段正常而且简便的写法，上面那种写法是分情况讨论而且非常阴间的：

非分类讨论写法（大家经常是这么写的）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs2 (int p, int fath)
{
	dfsn[p] = ++ dfsn[0]; // 用 dfsn[0] 的这个空间来记当前的序号，等价于 cnt
	top[p] = fath;
	rev[dfsn[0]] = a[p];
	if (!hson[p]) 
		return;
	dfs2 (hson[p], fath);
	for (int i = head[p]; ~i; i = edge[i].nxt)
	{
		int v = edge[i].to;
		if(v == fa[p] || v == hson[p]) 
			continue;
		dfs2 (v, v); // 重开一条链
	}
}

分类讨论写法（我经常是这么写的，不过也不乏有人用这种方法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs2 (int p, int fath)
{
	if (hson[p])
	{
		dfsn[hson[p]] = ++ dfsn[0];
		top[hson[p]] = top[p];
		rank[dfsn[0]] = hson[p];
		dfs2 (hson[p], p);
	}
	for (int i = head[p]; ~i; i = edge[i].nxt)
	{
		int v = edge[i].to;
		if (!top[v])
		{
			dfsn[v] = ++ dfsn[0];
			rank[dfsn[0]] = v;
			top[v] = v;
			dfs2 (v, p);
		}
	}
}

注意到，每棵子树的 序都是连续的，且根节点的 序最小；而且，如果我们优先遍历重子节点，那么同一条链上的节点的 序也是连续的，且链头节点的 序最小，叶节点的 是最大的。

是连续的！连续的！

所以就可以用线段树等数据结构维护区间信息，例如接下来讲的路径修改，可以转化为线段树的区间修改。

路径修改

只要搞清楚转移和区间修改时端点就差不多了， 函数请在《二分光辉线段树》查看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void update (int x, int y, int z) // 路径修改
// 修改 x 到 y 区间
{
	while (top[x] != top[y]) // 如果目前两者不在同一条链上
	{
		if (dep[top[x]] < dep[top[y]]) // 在未在同一条链上时，我们需要让链头较深的点跳上去
			swap (x, y); // 我们保证 x 的链头较深
		update (1, 1, n, dfsn[top[x]], dfsn[x], z); // 从 x 的链头到 x 做修改
		x = fa[top[x]]; // 转移到另一条链上
	}
	if (dep[x] > dep[y]) // 此时两者已在同一条链上，我们保证 x 在 y 下面
		swap (x, y);
	update (1, 1, n, dfsn[x], dfsn[y], z);
}

在未在同一条链时，为什么要让链头较深的点先往上跳？

假设我们现在要对着这张图幻想计算 号节点和 号节点的最短路径：

来幻想计算！（好吧就是模拟）

那么我们看一下它们的链头在什么位置：

emmm就是这样！

然后如果我们无所谓地跳，如果是让链头较浅的 号点先跳：

那么这时跳到1号点

那再让 号点跳到 号点，就会出现一些显而易见的小问题：

出问题啦！

我们发现，多出了一段 的路径！虽然可以减掉，但是太麻烦了，所以我们规定先让链头较深的点跳：

这样就没问题了嘛

路径查询

与路径修改没啥区别，基本操作都交给线段树，我们树链剖分只负责给出区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int query_path (int x, int y) // 路径查询 
// 这里以求和为例，基本结构与上面的路径修改相同，不懂的可以去问它  
{
	int ans = 0;
	while (top[x] != top[y])  
	{
		if (dep[top[x]] > dep[top[y]])
		{
			ans += query (dfsn[top[x]], dfsn[top[y]]); // 唯一区别就是把修改改成了查询权和 
			x = fa[top[x]];
		}
		else
		{
			ans += query (dfsn[top[y]], dfsn[top[x]]);
			y = fa[top[y]];
		}
	}
	if (dep[x] > dep[y])
		ans += query (dfsn[y], dfsn[x]);
	else
		ans += query (dfsn[x], dfsn[y]);
	return ans;
}

子树修改

如果是一棵子树，那么区间就是从这个点到叶节点，而叶节点恰是那个子树里 序最大的那个，所以：

1
2
3
4
void update_subtree (int x, int z) // 子树修改 
{
	update (dfsn[x], madfsn[x], z); // 一切交给线段树
}

子树查询

大概应该差不多几乎相同吧：

1
2
3
4
int query_subtree (int x) // 子树查询
{
	return query (dfsn[x], madfsn[x]); // 一切交给线段树
}

建线段树

需要注意，建线段树时要按 序建，所以要把 的代码板子背得滚瓜烂熟。

1
2
3
4
for (int i = 1; i <= n; i ++)
	scanf ("%d", &b[i]);
for (int i = 1; i <= n; i ++)
	a[dfsn[i]] = b[i]; // 按 dfs 序建

当然，不仅可以用线段树维护，也可以用珂朵莉树等数据结构（很看数据），如果需要维护的是边权而不是点权，就把每条边的边权下放到深度较深的那个点就可，但是查询和修改的时候要记得略过最后一个点。

长链剖分

其实长链剖分和重链剖分没啥区别，但是看看名字都不一样所以定义也同样不同。

定义

重子节点：表示其子节点中子树深度最大的子节点，如果有多个子树最大的子节点，取其一，如果没有节点就无重子节点。

轻子节点：表示剩余的子节点。

重边：这个节点到重子节点的边为重边。

轻边：到其他轻子节点的边为轻边。

重链：若干条首尾衔接的重边构成重链

我，一棵被长链剖分的树

然后你会发现其实我是直接把上面的那张图搬下来的，反正也符合长链剖分的法则。

所有链的长度的和都是 级别的，因为所有点在且仅在一条重链之中，永远只会被计算一次；任意一个点的 次祖先 所在的重链的长度大于等于 ，假如这个祖先的所在的重链长度小于 ，那么它所在的链一定不是重链，因为 这条链更优，那么祖先所在重链长度至少为 ，性质成立，反则亦之；还有就是，任何一个点向上跳跃重链的次数不会超过 次，跳跃后到的重链长度不会小于前面这条重链长度，那么在最坏情况下也就是 次。

长链剖分的食用

代码其实也没啥不同，无非是我们的规则现在变成了子树深度最大的那个点作为重儿子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void dfs1 (int u, int fath)
{
	maxdep[u] = dep[u] = dep[fath] ++;
	fa[u] = fath;
	for (int head[u]; i; i = edge[i].nxt)
	{
		int v = edge[i].to;
		if (v == fath)
			continue;
		dfs1 (v, u);
		if (maxdep[v] > maxdep[hson[u]])
		{
			hson[u] = v;
			maxdep[u] = maxdep[v];
		}
	}
}
void dfs2 (int u, int p)
{
	top[u] = p;
	len[u] = maxdep[u] - dep[top[u]] + 1;
	if (hson[u])
		dfs2 (hson[u], p);
	for (int i = head[u]; i; i = edge[i].nxt)
		if (edge[i].to != fa[u] && edge[i].to != hson[u])
			dfs2 (edge[i].to, edge[i].to);
}

计算k次祖先

有好几种方法，可以树链剖分之后跳重链，这样是 的，当然也可以提前预处理好倍增数组，这样是 的，还可以对于每个点暴力维护 次祖先，这样是 的，如果支持离线的话甚至可以做到 ，只需要在 的时候维护一个栈就可以了。

然后其实最优可以达到预处理 ，单次询问 的方法，主要就是利用这个点和它的 级祖先是一条链上的蚂蚱的性质。

代码老简单了，但是我就是不会：

1
2
3
4
5
6
7
8
9
10
inline int query (int x, int k) // 求 k 级祖先  
{
	if (!k)
		return x;
	x = fa[x][log2[k]];
	k -= 1 << log2[k];
	k -= dep[x] - dep[top[x]];
	x = top[x];
	return k >= 0 ? nodeup[x][k] : nodedown[x][-k]; // 抉择是上是下  
}