长链剖分

回顾

注意到，有一个和它名字特别相近的算法叫做 重链剖分。它是每一次找到大小最大的儿子作为重儿子，这样树的规模就至少缩小了 $\frac{1}{2}$，于是从底部的某一个节点到达根节点的重链数量最多也就 $O(\log n)$ 个。

它可以帮助我们解决很多问题。比如说我们要在树上维护路径加路径求和，那么就需要它帮助我们在 $O(q \log ^2 n)$ 的复杂度内完成题目。

正文

定义

作为一个较为重要的辅助工具，我们需要一些定义：

  • 重儿子： 最大深度最大的一个儿子。形式化的，$son_u = \operatorname{Id} (\max\limits_{v\in son_u} len_v)$，其中 $len_u$ 表示 $u$ 子树中的最大深度。
  • 重边： 一个点到它重儿子的那条边叫做重边。形式化的，集合 $E = { (u, son_u)}$ 的元素叫做重边。
  • 重链的顶端： 若一个点 $u$ 不是它父亲的重儿子，那么它是一条重链的顶端。形式化的，集合 $V = {u\mid u \not = son_{fa_u}}$ 中的点叫做重链的顶端。
  • 重链： 从一个重链的顶点出发，不断跳它的重儿子产生的链叫做重链。形式化的，我们设 $x$ 为一个重链的端点，$y$ 为一个叶子结点，且它们在一条重链上，则称集合 ${(x, y)}$ 中的元素为重链。

预处理

与 重链剖分 类似的，我们改一改求 $son_u$ 的过程即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs1(int x){
	dep[x] = dep[fa[x][0]] + 1, mx[x] = 1;
	for(int i=1;i<=t;++i)
		fa[x][i] = fa[fa[x][i-1]][i-1];
	for(int y:g[x]){
		if(y==fa[x][0])	continue;
		dfs1(y);
		if(mx[y]>mx[son[x]])	son[x] = y;
	}
	mx[x] = mx[son[x]] + 1;
}
void dfs2(int x, int tp){
	top[x] = tp;
	if(x==tp){
		for(int i = 1, xx = x; i<=mx[x]; ++i, xx = fa[xx][0]) fd[x].pb(xx);
		for(int i = 1, xx = x; i<=mx[x]; ++i, xx = son[xx])	sd[x].pb(xx);
	}
	if(son[x])	dfs2(son[x], tp);
	for(int y:g[x])
		if(y!=fa[x][0]&&y!=son[x])	dfs2(y, y);
}

性质

  • 我们设所有重链的顶点的集合为 $V$，则 $\sum\limits_{u\in V} mx_u = n$。即所有重链的长度和等于 $n$。

    证明

    显然，对于一个点 $u$ 它属于且仅属于一条重链。于是得证。

  • 若一个点 $x$ 的 $k$ 级祖先为 $y$，则 $y$ 所在的重链的长度至少为 $k$。

    证明

    显然，因为 $y$ 的深度至少为 $x$，$y$ 所在的重链再小也不会小于 $x$ 到 $y$ 的距离。因此至少为 $k$。

  • 树中的任意一个点 $x$ 到达根节点的路径上走过的长链数量最多为 $O(\sqrt n)$ 个。

    证明

    考虑如何构造一个树使得它达到 $O(\sqrt n)$ 的长链数量。我们设树上一共有 $O(n^2)$ 个点，而且是一棵二叉树。那么每个节点的左儿子是一个深度为 $n$ 的链，而右儿子是一个和当前节点形态基本一致的。也就是说，右儿子节点也是左儿子一条链右儿子形态一样，这样就保证了我们每一次都会选择左儿子当做重儿子，把右儿子当做轻儿子，于是最右下的那个点到根节点也就经过了 $O(n)$ 条长链。数量级也就是 $O(\sqrt n)$ 的。

应用

求树上的 $k$ 级祖先

方法一

首先我们可以想到使用倍增解决，复杂度 $O(n
log n) - O(\log n)$。

方法二

使用树链剖分解决这个问题也是不错的选择，可以先跳重链来确定 $k$ 级祖先在哪一个重链上，然后通过 $\operatorname{dfn}$ 序就可以 $O(1)$ 求出 $k$ 级祖先。复杂度 $O(n) - O(\log n)$。

方法三

也就是长链剖分了。

我们需要需处理两个东西：

  1. 和倍增一样的，我们需要维护每个节点的二的非负次幂级祖先在哪里。
  2. 对于每一个重链的端点，我们设该重链的深度为 $d$，那么我们要记录它所在的重链和它的 $1-d$ 级祖先。

首先我们证明它们复杂度的正确性。第一条肯定是正确的，我们在倍增的时候已经使用过它了。关于第二条，由长链剖分的性质，我们知道所有 $\sum\limits_{u\in V} dep_u = n$，也就是说，我们记录所有长链和与长链相等的祖先的信息，最多记录 $O(n)$ 条。这也就保证了第二个预处理的复杂度。

其次，我们叙述算法过程。

  1. 首先，找到最大的 $i$ 使得 $2^i\le k$。并且令：
    $$x\leftarrow top_{fa_{x, 2^i}}$$
    $$k \leftarrow k-2^i$$
  2. 我们保证了 $i$ 的最大性，也就是说，$2^i\le k<2^{i+1}$。而对于更新完的 $k$，有 $0\le k< 2^i$，而我们通过长链剖分的性质可以知道，因为更新后的 $x$ 已经是某一个点的 $2^i$ 级祖先了，因此 $x$ 所在长链的顶点的深度一定会大于 $2^i$。因此，只要我们到达了更新后的 $x$ 节点，通过我们记录的第 $2$ 条信息，就可以 $O(1)$ 地查询 $k$ 级祖先。

CODE

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef unsigned int ui;
const int N = 5e5 + 10;
const int M = 1e6 + 10;

ui seed;
int n, q, fa[N][20], root, x, lst, k, dep[N], top[N], mx[N], son[N], t;
long long ans;
vector<int> g[N], fd[N], sd[N];

ui get(ui x){
	x ^= x << 13; x ^= x >> 17; x ^= x << 5;
	return seed = x; 
}

void dfs1(int x){
	dep[x] = dep[fa[x][0]] + 1, mx[x] = 1;
	for(int i=1;i<=t;++i)
		fa[x][i] = fa[fa[x][i-1]][i-1];
	for(int y:g[x]){
		if(y==fa[x][0])	continue;
		dfs1(y);
		if(mx[y]>mx[son[x]])	son[x] = y;
	}
	mx[x] = mx[son[x]] + 1;
}
void dfs2(int x, int tp){
	top[x] = tp;
	if(x==tp){
		for(int i = 1, xx = x; i<=mx[x]; ++i, xx = fa[xx][0]) fd[x].pb(xx);
		for(int i = 1, xx = x; i<=mx[x]; ++i, xx = son[xx])	sd[x].pb(xx);
	}
	if(son[x])	dfs2(son[x], tp);
	for(int y:g[x])
		if(y!=fa[x][0]&&y!=son[x])	dfs2(y, y);
}
int query(int x,int k){
	if(k==0)	return x;
	int tt = log(k) / log(2);
	x = fa[x][tt], k -= (1<<tt);
	int up = dep[x] - dep[top[x]];
	x = top[x], k-=up;
	if(k<0)	return sd[x][-k];
	else	return fd[x][k];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin>>n>>q>>seed; t = log(n) / log(2);
	for(int i=1; i<=n; ++i){
		cin>>fa[i][0];
		if(fa[i][0]==0)	root = i;
		g[i].pb(fa[i][0]), g[fa[i][0]].pb(i);
	}
	dfs1(root), dfs2(root, root);
	for(int i=1; i<=q; ++i){
		int x = (get(seed) ^ lst) % n + 1, k = (get(seed) ^ lst) % dep[x];
		lst = query(x, k);
		ans ^= 1ll * i * lst;
	}
	cout<<ans<<endl;
	return 0;
}

长链剖分优化动态规划

CF1009F

就是上一场模拟赛的 $F$ 题。这个题除了线段树合并以外，还可以使用长链剖分优化来实现线性做法。

我们已经知道需要记录每个节点每个深度有多少个节点。我们可以长链剖分之后，对于重重儿子，我们直接继承，而对于轻儿子，我们暴力合并。这样，因为每条重链只会被合并一次，因此我们就可以线性地完成此题。

对于写法，仍然有很多需要注意的地方。一来是继承的时候需要注意深度的改变。我们不能够直接原封不动的继承过来，而是要把所有的深度都加一。这里有两种解决方法：一是使用指针，让指针后移一位，然后在第一位加上当前节点；二是使用向量 vector，使用动态内存，但是要注意的是存的顺序是反的。也就是说，第 $0$ 个节点其实是深度最大的地方，而 $mx$ 个节点才是深度最小的地方。

这里提供 vector 写法的 Code：

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
43
44
45
46
47
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef unsigned int ui;
const int N = 1e6 + 10;
const int M = 1e6 + 10;

int n, dep[N], son[N], mx[N], fa[N], ans[N];
vector<int> g[N], f[N];

void dfs1(int x,int fat){
	fa[x] = fat, dep[x] = dep[fat] + 1, mx[x] = 1;
	for(int y:g[x])
		if(y!=fat){
			dfs1(y, x);
			if(mx[y]>mx[son[x]])	son[x] = y;
		}
	mx[x] = mx[son[x]] + 1;
}
void getans(int x){
	if(son[x])	getans(son[x]), swap(f[x], f[son[x]]), ans[x] = ans[son[x]];
	// cout<<x<<" "<<son[x]<<" "<<ans[son[x]]<<endl;
	f[x].pb(1);
	// for(int y:f[x])	cout<<y<<" ";
	// cout<<endl;
	for(int y:g[x])
		if(y!=fa[x]&&y!=son[x]){
			getans(y);
			for(int i = 0, j = mx[x] - mx[y] - 1; i<mx[y]; ++i, ++j){
				f[x][j] += f[y][i];
				if(f[x][j]>f[x][ans[x]] || f[x][j]==f[x][ans[x]] && j>ans[x])	ans[x] = j;
			}
		}
	if(f[x][mx[x]-1]>=f[x][ans[x]])	ans[x] = mx[x]-1;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin>>n;
	for(int i = 1, x, y; i<n; ++i)
		cin>>x>>y, g[x].pb(y), g[y].pb(x);
	dfs1(1, 0); getans(1);
	for(int i=1;i<=n;++i)
		cout<<mx[i] - ans[i] - 1<<endl;
	return 0;
}

P5904 HOT-Hotels

这里我就放出来给出的 $DP$ 状态和柿子吧，真不知道为什么会有人想到这个题。

我们设 $f_{u,j} = \sum\limits_{v\in \operatorname{subtree}(u)} [d(u,v)=j]$，$g_{u,j} = \sum\limits_{v_1, v_2\in \operatorname{subtree}(u), v_1\not = v_2}[\operatorname{dis}(\operatorname{lca}(v_1,v_2),v_1)=\operatorname{dis}(\operatorname{lca}(v_1,v_2),v_2)=\operatorname{dis}(\operatorname{lca}(v_1,v_2),u)+j]$。

于是我们有如下转移：

$$ans\leftarrow \sum_{u} g_{u,0}$$

$$ans\leftarrow \sum_{v_1,v_2\in \operatorname{son}(u),v_1\not = v_2} f_{v_1,j-1}\times g_{v_2,j+1}$$

$$g_{u,j}\leftarrow \sum_{x,y\in \operatorname{son}(u), x\not = y} f_{x, j-1} \times f_{y, j-1}$$

$$g_{u,j}\leftarrow \sum_{x\in \operatorname{son}(u)}g_{x, j+1}$$

$$f_{u,j}\leftarrow \sum_{v\in \operatorname{son}(u)}f_{x, j-1}$$

然后直接套长链剖分即可。

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
43
44
45
46
47
48
49
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef unsigned int ui;
const int N = 1e5 + 10;
const int M = 1e6 + 10;

int n, dep[N], mx[N], fa[N], son[N];
vector<int> v[N];
long long *f[N], *g[N], p[N<<2], *o = p, ans;

void dfs(int x,int fat){
	dep[x] = dep[fat] + 1, mx[x] = 1, fa[x] = fat;
	for(int y:v[x])
		if(y!=fat){
			dfs(y, x);
			if(mx[y]>mx[son[x]])	son[x] = y;
		}
	mx[x] = mx[son[x]] + 1;
}
void solve(int x){
	if(son[x])	f[son[x]] = f[x] + 1, g[son[x]] = g[x] - 1, solve(son[x]);
	f[x][0] = 1, ans += g[x][0];
	for(int y:v[x])
		if(y!=son[x]&&y!=fa[x]){
			f[y] = o, o += mx[y]<<1, g[y] = o, o += mx[y]<<1;
			solve(y);
			for(int i=0;i<mx[y];++i){
				if(i)	ans += f[x][i-1] * g[y][i];
				ans += f[y][i] * g[x][i+1];
			}
			for(int i=0;i<mx[y];++i){
				g[x][i+1] += f[x][i+1] * f[y][i];
				if(i)	g[x][i-1] += g[y][i];
				f[x][i+1] += f[y][i];
			}
		}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin>>n;
	for(int i = 1, x, y ; i<n; ++i)	cin>>x>>y, v[x].pb(y), v[y].pb(x);
	dfs(1, 0); f[1] = o, o += mx[1]<<1, g[1] = o, o += mx[1]<<1;
	solve(1);
	cout<<ans<<endl;
	return 0;
}