Dyd's Blog

He who has a strong enough why can bear almost any how.

长链剖分

Posted on Edited on In
Symbols count in article: 3.8k Reading time ≈ 3 mins.

与深度相关的时候较常用

长链剖分

引入

在树上，我们很多时候都是父节点的信息由所有子节点计算得到，此时启发式合并/重链剖分大部分情况下可以做到很不错的复杂度，但是，当维护的信息与深度相关，甚至是每一个深度都要计算，我们会考虑长链剖分来做的更好

长链剖分的思想类似于 dus on tree ，我们在计算父节点时直接把最长（最深）的儿子的信息继承了（实现时常用指针维护深度的变化），然后把其它儿子的信息暴力合并上去

关于空间，由于一共就 $n$ 个点，所以所有长链的长度和是 $n$ ，那么一共就只要 $O(n)$ 的空间；关于时间，每个长链自身只算一次（自下而上被继承），也只会被合并一次（合并到其它长链中），所以时间为 $O(2n) = O(n)$

另外，从任何一共点向上跳长链，次数不会超过 $\sqrt{n}$ 次，这虽然劣于重链剖分，但有时候有点用

例题

Dominant Indices

题意

给定一棵 $n \le 10^6$ 个节点以 $1$ 为根的树，定义 $d(x, k)$ 表示 $x$ 的子树中到 $x$ 距离为 $k$ 的点的个数，对于每个节点，求一个最小的 $k$ 使得 $d(x, k)$ 最大

思路

比较板子，用一个 pair 记录一下答案就好，主要是看看如何实现

代码

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
#include <bits/stdc++.h>
#define fi first
#define se second
using PII = std::pair<int, int>;
const int N = 1e6 + 100;
int n, h[N], idx = 0;
int son[N], len[N];
PII ans[N];
int dd[N], *d[N], *cur = dd + 1;
struct Edge{ int ne, ver; } e[N << 1];
void add(int x, int y){ e[idx] = {h[x], y}, h[x] = idx++; }
void dfs1(int x, int fa)
{
	for (int i = h[x], y; ~i; i = e[i].ne) if ((y = e[i].ver) != fa)
	{
		dfs1(y, x);
		if (len[y] > len[son[x]]) son[x] = y;
	}
	len[x] = len[son[x]] + 1;
}
void dfs2(int x, int fa)
{
	d[x][0] = 1, ans[x] = {1, 0};
	if (!son[x]) return ;
	d[son[x]] = d[x] + 1;
	dfs2(son[x], x);
	ans[x] = std::max(ans[x], {ans[son[x]].fi, ans[son[x]].se - 1});
	for (int i = h[x], y; ~i; i = e[i].ne) if ((y = e[i].ver) != fa && y != son[x])
	{
		d[y] = cur, cur += len[y];
		dfs2(y, x);
		for (int j = 1; j <= len[y]; ++j)
		{
			d[x][j] += d[y][j - 1];
			ans[x] = std::max(ans[x], {d[x][j], -j});
		}
	}
}
int main()
{
	scanf("%d", &n);
	memset(h + 1, -1, n << 2);
	for (int i = 1, u, v; i < n; ++i)
	{
		scanf("%d %d", &u, &v);
		add(u, v), add(v, u);
	}
	dfs1(1, 0);
	d[1] = cur, cur += len[1];
	dfs2(1, 0);
	for (int i = 1; i <= n; ++i) printf("%d\n", -ans[i].se);
	return 0;
}

例题二

HOT-Hotels 加强版

思路

考虑树形 dp ，满足条件的情况如图：

tu

设橙色的三个点为 $u, v, w$ ，记 $x = lca(u, v), y = lca(x, w)$ 有 $dis(u, x) = dis(v, x) = dis(x, y) + dis(y, w)$ ，我们搞那么多 lca 是因为树形 dp 只能在最高点统计答案

记 $d[x, j]$ 表示“到点 $x$ 的距离为 $j$ 的点的个数”，记 $g[x, j]$ 表示“满足 $dis(u, w) = dis(v, w) = dis(w, x) + j$ 的点对 $u, v$ 的个数，其中 $w = lca(u, v)$ ）”，那么对于 $x$ 的一个儿子 $y$ ：
$$
\begin{aligned}
& //这里还没有转移, d[x, j], g[x, j]的意义都还是只包括y以前的子树的 \\
& ans += d[y, j] * g[x][j + 1] \\
& ans += g[y, j] * d[x][j - 1] \\
& //这里进行g的转移 \\
& g[x][j + 1] += d[x][j + 1] * d[y][j] \\
& g[x][j - 1] += g[y][j] \\
& //这里进行d的转移 \\
& d[x][j + 1] += d[y][j] \\
\end{aligned}
$$
显然直接做是 $O(n^2)$ 的，考虑长剖优化，每次把长儿子的答案直接继承，可以优化到 $O(n)$ ，但要注意， $g[x][j - 1] \gets g[x][j]$ ，这意味着长儿子应该填到 $x$ 之前的空间里，所以 $x$ 的前、后都要预留 $len$ 的空间（相应的池子里应该开 $2n$ 的空间）

代码

注意 dfs2 的第二个 for 只能是 j < len[y] 不能是 j <= len[y] ，因为 $y$ 的子树里到 $y$ 的距离最长为 $len[y] - 1$ ，调用 $len[y]$ 会到奇怪的地方，上一个例题没有这个问题是因为上一次空间是递增向后分配的，后面都是 $0$ 调用了也每关系，但本题 $g$ 是向前向后都分配了的

更具体的，如图：

空间

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
#include <bits/stdc++.h>
using LL = long long;
const int N = 1e5 + 100;
int n, h[N], idx = 0;
struct Edge{ int ne, ver; } e[N << 1];
int len[N], son[N];
LL dd[N], gg[N << 1], *d[N], *g[N], *cd = dd + 1, *cg = gg + 1, ans = 0;
void add(int x, int y){ e[idx] = {h[x], y}, h[x] = idx++; }
void dfs1(int x, int fa)
{
    for (int i = h[x], y; ~i; i = e[i].ne) if ((y = e[i].ver) != fa)
    {
        dfs1(y, x);
        if (len[y] > len[son[x]]) son[x] = y;
    }
    len[x] = len[son[x]] + 1;
}
void dfs2(int x, int fa)
{
    d[x][0] = 1;
    if (!son[x]) return ;
    d[son[x]] = d[x] + 1, g[son[x]] = g[x] - 1;
    dfs2(son[x], x);
    ans += g[x][0];
    for (int i = h[x], y; ~i; i = e[i].ne) if ((y = e[i].ver) != fa && y != son[x])
    {
        cg += len[y];
        d[y] = cd, g[y] = cg;
        cd += len[y], cg += len[y];
        dfs2(y, x);
        for (int j = 0; j < len[y]; ++j)
        {
            ans += d[y][j] * g[x][j + 1];
            if (j) ans += g[y][j] * d[x][j - 1];
        }
        for (int j = 0; j < len[y]; ++j)
        {
            g[x][j + 1] += d[x][j + 1] * d[y][j];
            if (j) g[x][j - 1] += g[y][j];
            d[x][j + 1] += d[y][j];
        }
    }
}
int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 1, u, v; i < n; ++i)
    {
        scanf("%d %d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs1(1, 0);
    cg += len[1];
    d[1] = cd, g[1] = cg;
    cd += len[1], cg += len[1];
    dfs2(1, 0);
    printf("%lld\n", ans);
    return 0;
}