树链剖分小结

目录

• 什么是树链剖分
• 概念
• 设的变量
• 步骤
• 时间复杂度
• 例题

什么是树链剖分

树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、(BST)、(SPLAY)、线段树等）来维护每一条链。——百度百科

树链剖分就是维护轻、重链，然后用其他数据结构来维护。（一般用树状数组或线段树）

概念

重儿子：所有儿子中siz最大的结点

轻儿子：除了重儿子以外的儿子
（强调：一个节点出了重儿子以外的点都是轻儿子）

重边：与重儿子连成的边

轻边：与轻儿子连成的边

重链：由多条重边连接而成的路径

轻链：由多条轻边连接而成的路径（一般都只有一条）

设的变量

(fa[x])，(x)的父亲
(dep[x])，(x)的深度
(siz[x])，(x)的子树大小
(son[x])，(x)的重儿子
(dfn[x])，(x)的新的编号（做(dfs)的顺序）
(top[x])，(x)所在的重链的顶端节点
（强调：我们可以保证每个节点都在也只在一条重链里）
(rk[x])，(dfn[])为(x)的在树中的节点

步骤

一般是两遍(dfs)。

第一遍：求出(fa[],dep[],siz[],son[])

void dfs(int x)
{
	dep[x] = dep[fa[x]] + 1, siz[x] = 1;
	for (int p = tail[x], v; p; p = e[p].fr)
	{
		v = e[p].v; fa[v] = x;
		dfs(v), siz[x] += siz[v];
		if (siz[v] > siz[son[x]]) son[x] = v;
	}
}

第二遍：求出(dfn[],top[],rk[])

void dfs1(int x, int fat)
{
	dfn[x] = ++tot; rk[tot] = x; top[x] = fat;
	if (! son[x]) return;
	dfs1(son[x], fat);
	for (int p = tail[x], v; p; p = e[p].fr)
	{
		v = e[p].v;
		if (v == son[x]) continue;
		dfs1(v, v);
	}
}

我们之所以先(dfs)重儿子，是因为我们要保证一条重链上每个节点的(dfn[])是连续的。
这便于我们用数据结构维护。
有时可以不用求(rk[])。

时间复杂度

可以证明，为O(nlog^2n)

例题

[ZJOI2008]树的统计
[NOI2015]软件包管理器
[SDOI2011]染色
[SHOI2012]魔法树
[HAOI2015]树上操作
[HEOI2016/TJOI2016]树