Qinshihuang's Blog

tmc的小窝

0%

长链剖分

发表于

长链剖分是另一种树的剖分方式。其主要用途之一是加速以深度为下标的 dp 到 $O(n)$。

长链剖分过程

类比重链剖分，我们定义树上一个节点的向下深度 $d_u$ 为从这个点出发向下走最大的距离。可以用树形 dp 理解，即 $d_{\mathrm{leaf}}=1$，$d_u=\max\{d_v+1\}$。

同时如果一个点有儿子，我们就定义一个点的长儿子为 $v$ 中 $d_v$ 最大的点，相应的剩余的儿子就是短儿子。定义长链就是一个短点和它的长儿子链成的从上往下的链。

从这个定义中不难发现长链的一些性质：

  • 所有长链的长度和为 $O(n)$。
  • 任意一个节点 $u$ 的 $k$ 级祖先 $f$ 所在长链的长度不小于 $k$。如果小于 $k$，那么显然 $f-u$ 这条链比原长链更长，又因为长链是从一个节点向下的最长链，因此矛盾。
  • 从一个节点出发，不断从跳到当前长链所在链顶的父亲，一直跳到根节点，跳链次数为 $O(\sqrt n)$。如果一个节点 $u$ 从一条长链跳到了另外一条长链上，那么跳跃到的这条长链的长度不会小于之前的长链长度。最坏情况下，链长分别为 $1,2,⋯,n$，也就是最多跳跃 $\sqrt n$ 次。

如何构造数据卡满跳链次数

我们可以构造这么一棵二叉树 $\mathcal T$：

假设构造的二叉树参数为 $d$。若 $d\neq 0$, 则在左儿子构造一颗参数为 $d-1$ 的二叉树，在右儿子构造一个长度为 $2d-1$ 的链；若 $d=0$, 则我们可以直接构造一个单独叶节点，并且结束调用。

这样子构造一定可以将单独叶节点到根的路径全部为轻边且需要 $d^2$ 级别的节点数。

取 $d=\sqrt n$ 即可。

这样的性质说明在处理重链剖分处理的需要跳链的问题上，长链剖分复杂度一般劣于重链剖分。但是，在处理与深度相关的问题时，长链剖分有时却能取得优秀的复杂度。

例子：树上 $k$ 级祖先

给定一棵树和 $m$ 次询问，每次询问给出一个点 $u$ 和一个参数 $k$，你需要求出 $u$ 的 $k$ 级祖先。$n\le5\times10^5$，$m\le5\times10^6$。

算法 $1$

利用倍增算法暴力向上跳即可，复杂度 $O((n+m)\log n)$。

算法 $2$

利用长链剖分，向上跳，复杂度 $O(n+m\sqrt n)$。

算法 $3$

我们考虑将上面两种算法结合起来。

首先我们记 $t=\lfloor\log_2k\rfloor$，并且直接让 $u$ 向上跳 $2^t$ 级。记 $f$ 为 $u$ 的 $2^t$ 级祖先，那么由上面的性质可知 $f$ 所在长链长度 $d$ 一定大于等于 $2^t$。由不等式知 $k-2^t<2^t\le d$。因此如果我们处理出 $f$ 所在链头 $T$ 向上向下走 $1\sim d$ 次的祖先儿子，我们就可以通过先跳到 $T$ 再查表跳点的方式跳到 $u$ 的第 $k$ 级祖先。

预处理的时候需要处理每个链头的 $2d$ 的信息，这样的时间复杂度是 $O(\sum2d)=O(n)$，因为长链总长度为 $O(n)$。

因此总时间复杂度是 $O(n\log n+m)$，可以通过。

长链剖分优化 dp

一些 dp 方程中，常常会出现与深度相关的复杂度，一般来说复杂度常常是 $O(\sum i\cdot dep_i)=O(n^2)$ 的，而利用长链剖分来优化复杂度就可以少掉一个 $n$。

长链剖分优化的思想与树上启发式合并非常相似。树上启发式合并善于解决与子树大小相关的问题，可以将 $O(n^2)$ 的算法优化到 $O(n\log n)$。

这里的思想也是类似的。我们先计算出 $u$ 的长儿子的 dp 数组，然后不清空、直接将其贡献合并到 $u$ 上；然后枚举短儿子并求出答案，并直接加起来。

这样的时间复杂度怎么求？注意到暴力合并短儿子的时间复杂度是所有短儿子长链的长度和，也就是 $O(n)$ 的。

一般来说实现上要使用指针以方便地实现合并贡献这一步（其实就是直接拿走长儿子的 dp 数组）。

CF1009F

给定一棵以 $1$ 为根的树，生成一个 $n\times n$ 的矩阵 $D$，其中 $D_{i,j}$ 表示 $i$ 子树中距离 $i$ 为 $j$ 的点数。对于所有 $i$ 求 $j$ 使得 $D_{i,j}=\max\limits_{0\le k<n}D_{i,k}$ 且 $j$ 最小。$n\le10^6$。

考虑暴力 dp，设 $dp_{u,i}$ 表示从 $u$ 向下的深度累计数组，那么

发现这东西下标和深度有关，因此套上长链剖分优化的板子，就变成了 $O(n\log n)$。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int n,fa[N],ans[N],dep[N],son[N];
int dfn[N],tim;
int *f[N],g[N];		//g是内存条
il void dfs(int u,int fa) {
	dep[u]=1;
	for(int i=head[u];i;i=edge[i].nxt) {
		int v=edge[i].v;
		if(v==fa) continue;
		dfs(v,u);
		dep[u]=max(dep[u],dep[v]+1);
		if(dep[v]>dep[son[u]]) son[u]=v;
	}
}
il void dfs2(int u,int fa) {
	dfn[u]=++tim;
	f[u]=g+dfn[u];
	if(son[u]) dfs2(son[u],u);
	for(int i=head[u];i;i=edge[i].nxt) {
		int v=edge[i].v;
		if(v==fa||v==son[u]) continue;
		dfs2(v,u);
	}
}
il void DP(int u,int fa) {
	if(son[u]) {
		DP(son[u],u);
		ans[u]=ans[son[u]]+1;
	}
	f[u][0]=1;
	if(f[u][ans[u]]<=1) ans[u]=0;
	for(int i=head[u];i;i=edge[i].nxt) {
		int v=edge[i].v;
		if(v==fa||v==son[u]) continue;
		DP(v,u);
		int len=dep[v];
		for(int j=0;j<len;j++) {
			f[u][j+1]+=f[v][j];
			if(f[u][j+1]>f[u][ans[u]]) ans[u]=j+1;
			else if(f[u][j+1]==f[u][ans[u]]&&j+1<ans[u]) ans[u]=j+1;
		}
	}
}

P5904

给定一棵树，边长为 $1$，统计满足以下条件的无序数对 $(x,y,z)$ 的组数：

  • $1\le x,y,z\le n$；
  • $\operatorname{dis}(x,y)=\operatorname{dis}(x,z)=\operatorname{dis}(y,z)$。

非常抽象的 dp。令 $f_{u,i}$ 表示从 $u$ 向下走 $i$ 步的节点数量，$g_{u,i}$ 表示

其中 $\mathrm{lca}$ 是 $x,y$ 的最近公共祖先。

那么可以求解 dp 转移方程：

答案就是

很显然可以通过前缀和优化、或者通过点按照顺序合并到父亲上的方式将其优化到 $O(dep)$ 转移、$O(n)$ 求解答案。

注意到转移方程和下标有关，因此上长链剖分即可。注意空间要开大约 $4$ 倍，因为 $g$ 的转移中下标一维是加而不是减，这要求我们向前分配空间，因此 $g_u$ 对应的指针前后都要留出 $d_u$ 的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ll *f[N],*g[N],p[N<<2],*ptr=p,ans=0;
il void dp(int u,int fa) {
	if(son[u]) {
		f[son[u]]=f[u]+1,g[son[u]]=g[u]-1;
		dp(son[u],u);
	}
	f[u][0]=1;
	ans+=g[u][0];
	for(auto v:G[u]) {
		if(v==fa||v==son[u]) continue;
		f[v]=ptr,ptr+=(dep[v]<<1);	//分配空间
		g[v]=ptr,ptr+=(dep[v]<<1);
		dp(v,u);
		for(int i=0;i<=dep[v];i++) {	//按序合并答案、同时利用 f[i],g[i] 来前缀和求解
			if(i!=0) ans+=f[u][i-1]*g[v][i];
			ans+=g[u][i+1]*f[v][i];
		}
		for(int i=0;i<=dep[v];i++) {
			g[u][i+1]+=f[u][i+1]*f[v][i];
			if(i!=0) g[u][i-1]+=g[v][i];
			f[u][i+1]+=f[v][i];
		}
	}
}

P3899

定义一棵以 $1$ 为根的树上两个不同的点 $u,v$ 的两种关系：

  • 若 $u$ 是 $v$ 的祖先，称 $u$ 比 $v$ 厉害。
  • 若对于一个常数 $k$，$\operatorname{dis}(u,v)\le k$ 则称 $u,v$ 彼此彼此。

给定一棵树和 $q$ 次询问，每次询问给出两个整数 $u,k$，要求统计对于 $k$，有多少对有序点对 $(a,b)$ 满足：

  • $u,a,b$ 两两不同，且 $u,a$ 都比 $b$ 厉害；
  • $u,a$ 彼此彼此。

根据这个关系不难发现：$u,a,b$ 是树上一条直上直下的链且 $b$ 最深，$\operatorname{dis}(u,a)\le k$。

定义根节点的深度为 $1$，如果 $dep_adep_u$。

我们不妨设 $dp_{u,i}$ 表示 $u$ 子树中、距离 $u$ 小于等于 $i$ 的点子树大小减 $1$ 的和，即

那么显然可得到转移方程

这里下标也是深度，利用长链剖分优化。但是注意到所有的 $dp_{v,i}$ 都要加上一个统一的常数 $siz_v-1$，无法快速更新合并。因此使用懒标记，定义 $tag_u$ 为所有 $dp_{u,i}$ 应当统一加上的值，那么就无需处理常数，只需要在合并的时候让 $tag_u\leftarrow tag_v+siz_v-1$ 即可。时间复杂度 $O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
il void dfs2(int u,int fa) {
	if(son[u]) {
		dp[son[u]]=dp[u]+1;
		dfs2(son[u],u);
		tag[u]=tag[son[u]]+siz[son[u]]-1;
	}
	for(auto v:g[u]) {
		if(v==fa||v==son[u]) continue;
		dp[v]=ptr,ptr+=d[v];
		dfs2(v,u);
		tag[u]+=tag[v]+siz[v]-1;	//合并标记
		for(int i=0;i<d[v];i++) dp[u][i+1]+=dp[v][i];
	}
	dp[u][0]=-tag[u];	//因为dp[u][0]应该是0，为了抵消tag[u]的影响要设为-tag[u]
	for(auto pp:que[u]) {	//离线处理
		ll k=pp.first,id=pp.second;
		ans[id]=dp[u][min(k,d[u]-1)]+tag[u];
	}
}