树链剖分

Summary

树链剖分（Heavy-Light Decomposition，HLD）把每个非叶节点子树最大的儿子定为重儿子，连向重儿子的边称重边，首尾相接的重边构成一条重链。经过两遍 DFS 处理后，同一条重链上的节点 DFS 序连续，且树上任意一条路径至多经过 O(logn) 条重链。于是对路径与子树的修改、查询都能拆成 O(logn) 段连续区间，交给线段树等区间结构处理。文中给出两遍 DFS 的实现：第一遍求出每个点的父亲、深度、子树大小并选出重儿子，第二遍按重链优先的顺序分配 DFS 序，得到的剖分还能直接用于快速求 LCA。

参考资料

• 树链剖分 - OI Wiki

简介

树链剖分（Heavy-Light Decomposition，HLD）把每个非叶节点子树最大的儿子定为 重儿子，连向重儿子的边为重边，重边相连成 重链。两遍 DFS 后，每条重链的 DFS 序连续，且任意树上路径至多经过 $O(\log n)$ 条重链。于是树上路径与子树的修改、查询都能转化为 $O(\log n)$ 段连续区间，配合线段树解决。

实现

447 Bcpp

vector<int> G[N];
int fa[N],son[N],siz[N],dep[N];
int top[N],dfn[N],rnk[N],out[N];
int cnt=0;
void dfs1(int u)
{
	siz[u]=1;
	dep[u]=dep[fa[u]]+1;
	for(auto v:G[u])
	{
		if(v==fa[u])continue;
		fa[v]=u;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int t)
{
	top[u]=t;
	dfn[u]=++cnt;
	rnk[cnt]=u;
	if(son[u])dfs2(son[u],t);
	for(auto v:G[u])
	{
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
	out[u]=cnt;
}

应用

详见 最近公共祖先。

例题

洛谷 P3384 【模板】重链剖分 / 树链剖分

给定一棵 $n$ 个结点的树，每个节点上包含一个数值，支持以下操作：

• 1 x y z：表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。
• 2 x y：表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。
• 3 x z：表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。
• 4 x：表示求以 $x$ 为根节点的子树内所有节点值之和。

洛谷 P5903 【模板】树上 K 级祖先

给定一棵 $n$ 个点的有根树。

有 $q$ 次询问，第 $i$ 次询问给定 $x_i, k_i$，要求点 $x_i$ 的 $k_i$ 级祖先，答案为 $ans_i$。特别地，$ans_0=0$。

洛谷 P3379 【模板】最近公共祖先（LCA）

给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

洛谷 P2590 [ZJOI2008] 树的统计

一棵树上有 $n$ 个节点，每个节点都有一个权值 $w_i$，支持以下操作：

• CHANGE u t：把结点 $u$ 的权值改为 $t$。
• QMAX u v：询问从点 $u$ 到点 $v$ 的路径上的节点的最大权值。
• QSUM u v：询问从点 $u$ 到点 $v$ 的路径上的节点的权值和。