诸老师我们喜欢你🥰💕

不出所料大概是网络赛前的最后一篇学习笔记了。之后得靠题目来查漏补缺了。

说实话一个暑假学的真爽啊。没有学期内大量的课业负担，可劲梭哈。

概述

树链剖分现今已经成为了竞赛选手必学的图论算法之一。其中最为出名也最为常见的是重链剖分，它通过把树划分成若干条重链，根据整条链和子树内的dfs序号连续的性质，再结合一些数据结构，能够很好地处理各类树链和子树的查询和修改问题。但树链剖分的另一个部分——长链剖分，虽然少见，但在特定情况下能够发挥出奇效。

长剖的做法和重剖类似，重链剖分靠子节点为根的子树大小来决定重儿子，而长链剖分通过子节点为根的子树高度来决定长儿子。剖分策略的不同导致二者具有截然不同的性质。在重剖里，一个节点向上跳跃到根节点最多经过 $O(\log{n})$ 条重链，而长剖不同，跳跃到根节点最多经过 $O(\sqrt{n})$ 条长链。这也很好证明，显然每次经过的长链的链长是递增的，最坏情况下经过的链长是 $1,2,\cdots,\sqrt{n}$ 的等差数列，因此最坏复杂度是 $O(\sqrt{n})$ 。这个性质注定了长剖和重剖的用途大相径庭。

事实上，长剖往往用于树上与深度相关的DP优化，既能优化时间，也能优化空间。类似dsu on tree的做法，我们让每个点直接继承长儿子的信息，再把短儿子的信息暴力合并进当前节点。容易发现每个点至多会被暴力合并一次，所以均摊下来整体时间复杂度是 $O(n)$ 的。同时注意到每条长链的信息可以共用，我们让每条长链使用同一块空间，所以空间复杂度也可以优化到 $O(n)$ 。具体在题目中进行解释。

例题

P5903 【模板】树上 K 级祖先

给定一棵树，$q$ 次询问节点 $u$ 的 $k$ 级祖先。强制在线。$q \le 10^{6}$ 。

$k$ 级祖先显然可以通过倍增来单次 $O(\log{n})$ 查询。但这道题 $q \le 10^{6}$ ，需要快速的查询方式。

长链剖分可以做到 $O(n\log{n})$ 时间预处理，之后单次 $O(1)$ 查询。

长链剖分有一个比较明显的性质：点 $u$ 的第 $k$ 级祖先所在的长链的长度大于等于 $k$ 。反证法可以证明。

我们预处理以下几个信息：点 $u$ 的第 $2^{i}$ 级祖先 $fa[u][i]$ ，即正常的倍增表；对每条长链的链头 $t$ ，维护其向链方向向下走 $i$ 步到达的点 $down[t][i]$ 和其向祖先方向向上走 $i$ 步到达的点 $up[t][i]$ 。上下方向维护的最大步长和链长相等，这样就可以在 $O(n)$ 的空间内保存。

查询时按照如下策略进行：先拿到 $k$ 的最高位 $b$ ，先让 $u$ 向上跳跃 $2^{b}$ 步，即跳到 $fa[u][b]$ 。再跳到该节点所在的链头，即 $top[fa[u][b]]$ ，同时记录此时的高度和目标高度的差值。令 $k’=k-2^{b}$ ，显然 $k’ < 2^{b}$ 。由上面的性质，显然链头维护的上下高度区间长度大于 $2k’$ ，我们根据剩余的高度差值在 $up$ 或 $down$ 中查表即可。

$k$ 级祖先和高度的关联在于，每级祖先的高度都会递减，因此可以借助长链剖分来优化。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 5e5 + 10;
constexpr int MOD = 998244353;

u32 s;

inline u32 get(u32 x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return s = x; 
}

vector<int> e[N];
int fa[N][20];
int top[N], len[N], son[N], d[N], dfn[N], up[N], down[N];
int n, q, idx;

void dfs1(int u, int f) {
    d[u] = d[f] + 1;
    fa[u][0] = f;
    for (int i = 1; i < 20; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int v : e[u]) {
        if (v == f) continue;
        dfs1(v, u);
        if (len[son[u]] < len[v]) son[u] = v;
    }
    len[u] = len[son[u]] + 1;
}

void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++idx;
    if (u == t) {
        for (int i = 0, x = u; i < len[u]; ++i, x = son[x]) down[dfn[u] + i] = x;
        for (int i = 0, x = u; i < len[u]; ++i, x = fa[x][0]) up[dfn[u] + i] = x;
    }
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int v : e[u]) {
        if (top[v]) continue;
        dfs2(v, v);
    }
}

int query(int u, int k) {
    if (!k) return u;
    int t = __lg(k);
    if (k == (1 << t)) return fa[u][t];
    k -= 1 << t;
    u = fa[u][t];
    k -= d[u] - d[top[u]];
    u = top[u];
    return k >= 0 ? up[dfn[u] + k] : down[dfn[u] - k];
}

void solve() {
    cin >> n >> q >> s;
    int rt;
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        if (!x) rt = i;
        else {
            e[i].push_back(x);
            e[x].push_back(i);
        }
    }
    dfs1(rt, 0);
    dfs2(rt, rt);
    i64 ans = 0;
    for (int i = 1, lastAns = 0, x, k; i <= q; ++i) {
        x = (get(s) ^ lastAns) % n + 1, k = (get(s) ^ lastAns) % d[x];
        ans ^= 1LL * i * (lastAns = query(x, k));
    }
    cout << ans << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P10641 BZOJ3252 攻略

给定一棵树，点带点权，选 $k$ 条根节点到叶子结点的简单路径，求路径交集点权之和的最大值。

我们扩展一下长剖的定义。

正常的长剖做法是，每个点选取子节点为根的子树高度最大的那个节点作为长儿子，本道题选取子节点作为链头的链点权之和最大的那个节点作为儿子。按照这个策略进行剖分，可以把原树的点不重不漏的恰好分成若干组。将所有链的点权和统计好排序，计算前 $k$ 大的前缀和即可。

合法性这样证明：显然一个链唯一对应一个链头，我们只考虑链头是否被选取。一个非根节点如果是链头，说明这条链的链权小于等于其不是链头的兄弟节点（即连向祖先的更大权链的那个点）及以下的链权。如果这条链被选取，那么其父亲必然在其之前被选取，所以不会出现一个点被选取而其父亲未被选取的情况，所以这样做是正确的。

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
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<i64> w(n + 1);
    for (int i = 1; i <= n; ++i) cin >> w[i];
    vector<vector<int>> e(n + 1);
    vector<int> son(n + 1), top(n + 1);
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    auto dfs1 = [&](auto&& dfs1, int u, int f) -> void {
        for (int v : e[u]) {
            if (v == f) continue;
            dfs1(dfs1, v, u);
            if (w[son[u]] < w[v]) son[u] = v;
        }
        w[u] += w[son[u]];
    };
    auto dfs2 = [&](auto&& dfs2, int u, int t) -> void {
        top[u] = t;
        if (!son[u]) return;
        dfs2(dfs2, son[u], u);
        for (int v : e[u]) {
            if (top[v]) continue;
            dfs2(dfs2, v, v);
        }
    };
    dfs1(dfs1, 1, 0);
    dfs2(dfs2, 1, 1);
    vector<i64> v;
    v.reserve(n);
    for (int i = 1; i <= n; ++i) {
        if (top[i] == i) v.push_back(w[i]);
    }
    ranges::sort(v, greater<i64>());
    i64 ans = 0;
    for (int i = 0; i < k && i < v.size(); ++i) ans += v[i];
    cout << ans << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

CF1009F Dominant Indices

求每个点 $u$ 的最小深度 $h$ ，使得以 $u$ 为根的子树内深度为 $h$ 的节点数量最多。

万年典题，多少人长剖优化DP的入门题也是唯一一题。

定义 $f[u][i]$ 为以 $u$ 为根的子树内深度为 $i$ 的节点数量。那么点 $u$ 和其子节点 $v$ 的转移为 $f[u][i] \leftarrow f[u][i] + f[v][i-1]$ 。

显然每个点的最大深度就是其长剖时计算的 $len[u]$ 。我们发现一条长链中相邻的节点均满足这个转移关系，因此让每条长链公用同一块数组空间，转移时将非长儿子的节点合并。每个点仅会被合并一次，同时长链内部的转移相当于直接被每个点的祖先继承，既优化了空间，也优化了时间，复杂度均为 $O(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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> e(n + 1);
    vector<int> len(n + 1), son(n + 1), dfn(n + 1), dp(n + 1), ans(n + 1);
    int idx = 0;
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    auto dfs1 = [&](auto&& dfs1, int u, int f) -> void {
        for (int v : e[u]) {
            if (v == f) continue;
            dfs1(dfs1, v, u);
            if (len[son[u]] < len[v]) son[u] = v;
        }
        len[u] = len[son[u]] + 1;
    };
    auto dfs2 = [&](auto&& dfs2, int u, int f) -> void {
        dfn[u] = ++idx;
        dp[dfn[u]] = 1;
        if (son[u]) {
            dfs2(dfs2, son[u], u);
            ans[u] = ans[son[u]] + 1;
        }
        for (int v : e[u]) {
            if (v == f || v == son[u]) continue;
            dfs2(dfs2, v, u);
            for (int i = 1; i <= len[v]; ++i) {
                dp[dfn[u] + i] += dp[dfn[v] + i - 1];
                if (dp[dfn[u] + i] > dp[dfn[u] + ans[u]] || (dp[dfn[u] + i] == dp[dfn[u] + ans[u]] && i < ans[u])) {
                    ans[u] = i;
                }
            }
        }
        if (dp[dfn[u] + ans[u]] == 1) ans[u] = 0;
    };
    dfs1(dfs1, 1, 0);
    dfs2(dfs2, 1, 0);
    for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P5904 [POI 2014] HOT-Hotels 加强版

给定一棵树，求其两两距离均相等的三元点组数量。

先考虑怎么不重不漏地计数。由于是在树上，显然三个点的路径会存在唯一交点。对于每个点，只考虑这个点在交点和三元组深度最小的点之间的路径上的情况，对应这个点被选取和三元组跨这个点的两种情况。

定义 $f[u][i]$ 为以 $u$ 为根的子树内深度为 $i$ 的点的数量，$g[u][i]$ 是满足 $d(x,z)=d(y,z)=d(z,u)+i$ 的点对 $(x,y)$ 的数量。显然如果 $(x,y)$ 唯一确定，那么 $z$ 就是二者的最近公共祖先，也被唯一确定。

$f[u][i]$ 的转移和上一题相同，不赘述；$g[u][i]$ 和其子节点 $v$ 的一种转移是 $g[u][i] \leftarrow g[u][i] + g[v][i+1]$ ，对于这种转移要怎么处理？

我们同样尝试让每条长链共享空间，不过这次由于 $g[u]$ 的定义，我们要为每个链头单独留出足够的空间，这样合并的时候才能保证信息正确。开一个长度为 $2n$ 的数组，每条链的链尾的位置放在其链头 $dfn$ 序的二倍对应的下标处，之后从链尾到链头按顺序依次摆放。按这种方式排列，链内父节点天然继承了 $g$ 中子节点的转移。同时，由于我们每次将链尾放在 $dfn$ 序的二倍处，那么每个链尾前的一段空间就能留给上一条链的链头来保存信息。这种方式会导致个别空间未被使用，但都是常数，空间复杂度还是 $O(n)$ 。

现在讨论 $g[u]$ 的其他转移。三元组分两种情况，一种是在当前 $u$ 为根的子树中选两个点，在子节点 $v$ 为根的子树中选一个点，反之亦然。所以有如下转移：$g[u][i] \leftarrow g[u][i] + g[u][i] \times f[v][i-1]$ ，$g[u][i] \leftarrow g[u][i] + f[u][i] \times g[v][i+1]$ 。这两种转移显然与长链无关，直接做合并。

每个点均摊下来只被合并一次，时间复杂度 $O(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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> e(n + 1);
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<int> len(n + 1), son(n + 1), dfn(n + 1), gid(n + 1);
    vector<i64> dp1(n + 1), dp2(2 * n + 1);
    int idx = 0;
    i64 ans = 0;
    auto dfs1 = [&](auto&& dfs1, int u, int f) -> void {
        for (int v : e[u]) {
            if (v == f) continue;
            dfs1(dfs1, v, u);
            if (len[son[u]] < len[v]) son[u] = v;
        }
        len[u] = len[son[u]] + 1;
    };
    auto dfs2 = [&](auto&& dfs2, int u, int t) -> void {
        dfn[u] = ++idx;
        if (!son[u]) {
            gid[u] = dfn[t] * 2;
            return;
        }
        dfs2(dfs2, son[u], t);
        for (int v : e[u]) {
            if (dfn[v]) continue;
            dfs2(dfs2, v, v);
        }
        gid[u] = gid[son[u]] + 1;
    };
    auto dfs3 = [&](auto&& dfs3, int u, int f) -> void {
        dp1[dfn[u]] = 1;
        if (!son[u]) return;
        dfs3(dfs3, son[u], u);
        for (int v : e[u]) {
            if (v == f || v == son[u]) continue;
            dfs3(dfs3, v, u);
            for (int i = 0; i <= len[v]; ++i) {
                if (i < len[u] && i > 0) ans += dp2[gid[u] + i] * dp1[dfn[v] + i - 1];
                if (i && i + 1 < len[v]) ans += dp1[dfn[u] + i] * dp2[gid[v] + i + 1];
            }
            for (int i = 0; i <= len[v]; ++i) {
                if (i + 1 < len[v]) dp2[gid[u] + i] += dp2[gid[v] + i + 1];
                if (i) dp2[gid[u] + i] += dp1[dfn[u] + i] * dp1[dfn[v] + i - 1];
                if (i) dp1[dfn[u] + i] += dp1[dfn[v] + i - 1];
            }
        }
        ans += dp2[gid[u]];
    };
    dfs1(dfs1, 1, 0);
    dfs2(dfs2, 1, 1);
    dfs3(dfs3, 1, 0);
    cout << ans << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

结语

说到底，长剖就是个小众又冷门的算法，很少作为考点出现在题目中。但一旦遇到了适合的使用场景，优化的效果还是很激动人心的。姑且出于理性愉悦的目的，辩证地学习吧。