轻重链剖分

本文主要是介绍轻重链剖分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 轻重链剖分
• 轻重链剖分基本原理
• 代码实现（板子）
  • 题面
  • 换根影响
  • 轻重链剖分
  • 链操作
  • 子树操作
  • 整体代码
• 树剖完就是线段树题了qwq
• 没了
• 题外话

轻重链剖分

论文鸽说叫 heavy-light decomposition 或 heavy path decomposition .

正确叫法（不是）：

这是真的：

轻重链剖分基本原理

一个节点子树大小最大的儿子叫重儿子 .

节点到重儿子的边叫重边 .

一堆重边叫重链 .

重儿子优先 DFS，于是重链连续，每条链可以拆成若干条重链和杂边 .

每次走轻儿子子树大小至少除以二，于是每条链可以拆成 \(\log\) 条重链，用线段树维护 DFS 序就可以做到 \(\log^2\) .

这就是轻重链剖分的基本原理 .

代码实现（板子）

题面

LOJ139 树链剖分

维护一棵 \(n\) 个点有点权的树，支持

• 换根
• 路径修改
• 子树修改
• 路径和
• 子树和

换根影响

树上两点间路径唯一，于是路径啥事没有

换根对子树的影响可以看 树 社论 的做法，就是拆成子树补啥的 .

于是做完了 .

轻重链剖分

轻重链剖分通过两次 dfs 完成，非常好理解吧 .

整理一下要维护的东西：

• 父亲
• 深度
• 子树大小
• 重儿子
• 所在重链顶端节点（top）
• DFS 序相关

Code:

void dfs1(int u)
{
	siz[u] = 1;
	for (int v : g[u])
	{
		if (v == fa[u]) continue;
		fa[v] = u;
		dep[v] = dep[u] + 1;
		dfs1(v);
		siz[u] += siz[v];
		if (!son[u] || (siz[v] > siz[son[u]])) son[u] = v;
	}
}
void dfs2(int u, int t)
{
	top[u] = t;
	rnk[++cc] = u; dfn[u] = cc;
	if (!son[u]) return ;
	dfs2(son[u], t);
	for (int v : g[u])
		if ((v != son[u]) && (v != fa[u])) dfs2(v, v);
}

链操作

查询修改类似

ll query(int u, int v)
{
	ll ans = 0, fu = top[u], fv = top[v];
	while (fu != fv)
	{
		if (dep[fu] > dep[fv]){ans += T.query(1, dfn[fu], dfn[u]); u = fa[fu];}
		else{ans += T.query(1, dfn[fv], dfn[v]); v = fa[fv];}
		fu = top[u]; fv = top[v];
	}
	if (dfn[u] > dfn[v]) swap(u, v);
	return ans + T.query(1, dfn[u], dfn[v]);
}

可以精简代码です

子树操作

DFS 序板子，略过 .

整体代码

Welcome to OI!

树剖完就是线段树题了qwq

没了

题外话

——《Segment Tree Beats!》
应该是圆方树解决吧 .

这篇关于轻重链剖分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！