重链剖分

一些记号

$u$ 的父节点为 $fa_u$，$u$ 子树的大小为 $siz_u$，$u$ 的重子节点为 $ws_u$，$u$ 所在重链中的深度最小节点为 $top_u$。

重链剖分，可以把树划分成若干条链。

怎么剖分呢？我们先看几个定义。

定义一个节点的重子节点为其子节点中子树最大的子结点中的其中一个。

定义一个节点的轻子节点为除了重子节点外剩余的所有子结点。

从一个结点到它的重子节点的边为重边。

从一个结点到它的轻子节点的边为轻边。

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

把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。

就像这样：

我们发现，这样剖出来的树有一些美好的性质。

1. 一条从某个点到根的路径上，经过的重链数量不超过轻边数量 $+1$。

   证明

   每两条重链之间至少有一条轻边，得证。

2. 一条从某个点到根的路径上，经过的重链数量不超过 $\log n$。

   证明

   当 $u$ 往 $fa_u$ 走的时候，每经过一条轻边，$u$ 的子树大小就会至少翻倍。

   为什么呢？如果 $u$ 与 $fa_u$ 之间的边是轻边，那么 $fa_u$ 的重子节点 $v$ 肯定满足 $siz_v \ge siz_u$。然后 $siz_{fa_u}$ 至少是 $siz_u + siz_v + 1 \ge 2siz_u$，得证。

由于性质二，一条从某个点到根的路径上，经过的重链数量也是 $\log$ 级别的。所以，我们可以借助重链剖分来解决许多问题。

先放上剖分代码：

void dfs(int u, int ft){
	int tmp = 0;
	siz[u] = 1;
	for (int i = head[u];i != -1;i = e[i].nxt){
		int v = e[i].v;
		if (v == ft) continue;
		fa[v] = u, dep[v] = dep[u] + 1, dfs(v, u), siz[u] += siz[v];
		if (siz[v] > tmp) tmp = siz[v], ws[u] = v;
	}
}
void dfs2(int u, int ft, int tp){
	top[u] = tp;
	if (ws[u]) dfs2(ws[u], u, tp);
	for (int i = head[u];i != -1;i = e[i].nxt){
		int v = e[i].v;
		if (v != ws[u] && v != ft) dfs2(v, u, v);
	}
}

重链剖分求 LCA

因为经过的重链数量也是 $\log$ 级别的，所以我们可以想到以下算法流程来求出 $\operatorname{lca}(u, v)$：

1. 如果 $u$ 和 $v$ 在同一条重链上（即 $top_u = top_v$），深度较小的即为答案。

2. 找出 $top_u$ 和 $top_v$ 中深度较浅的那个，设为 $x$，然后让 $x$ 跳到 $fa_{top_x}$。

3. 回到步骤一。

求 LCA 部分代码：

int lca(int u, int v){
	while (top[u] != top[v]){
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fa[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}

其实，在上面的证明中能发现 $\log n$ 只是经过重链数的一个上限，实际运行的时候是远远达不到这个上限的，所以重链剖分常数极小。

倍增 LCA 提交记录 重链剖分 LCA 提交记录

重链剖分实现维护静态树点权

【模板】重链剖分

给你一棵树，要求支持四种操作：链加，链求和，子树加，子树求和。

我们考虑用 DFS 序把树拍到序列上，然后用一棵线段树维护序列。

究竟怎么拍呢？我们设 $dfn_u$ 为 $u$ 的 DFS 序，将上面 dfs2 的代码略微改动一下：

void dfs2(int u, int tp){
	dfn[u] = ++ cnt, top[u] = tp;
	if (wson[u]) dfs2(wson[u], tp);
	for (int i = head[u];i != -1;i = e[i].nxt){
		int v = e[i].v;
		if (v == fa[u] || v == wson[u]) continue;
		dfs2(v, v);
	}
}

这里有一个细节，对于每一个节点 $u$，dfs2 中需要先遍历 $ws_u$，就可以使每一条重链的 DFS 序都相邻。

又因为 DFS 本身的性质，每一个子树所有节点的 DFS 序也在一个连续的区间里。

然后子树加直接用一次区间加来实现，子树求和直接用区间求和实现即可。

类比上面的重链剖分求 LCA，链加与链求和可以使用类似的过程跳点，并对经过的重链修改 / 加上答案。

放上四个操作的代码：

void linkadd(int u, int v, int x){ // 链加
	while (top[u] != top[v]){
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		update(1, 1, n, dfn[top[u]], dfn[u], x);
		u = fa[top[u]];
	}
	if (dep[u] > dep[v]) swap(u, v);
	update(1, 1, n, dfn[u], dfn[v], x);
}
void treeadd(int u, int x){ // 子树加
	update(1, 1, n, dfn[u], dfn[u] + siz[u] - 1, x);
}
int linksum(int u, int v){ // 链和
	int ans = 0;
	while (top[u] != top[v]){
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		ans = ((ll)ans + query(1, 1, n, dfn[top[u]], dfn[u])) % mod;
		u = fa[top[u]];
	}
	if (dep[u] > dep[v]) swap(u, v);
	ans = ((ll)ans + query(1, 1, n, dfn[u], dfn[v])) % mod;
	return ans;
}
int treesum(int u){ // 子树和
	return query(1, 1, n, dfn[u], dfn[u] + siz[u] - 1);
}

于是，子树操作的时间复杂度为 $O(\log n)$，链操作的时间复杂度为 $O(\log^2 n)$。

例题

[NOI2015] 软件包管理器