长链剖分

https://blunt-axe.github.io/2019/11/25/20191125-Longest-Decomposition-Notes/

Problem - E - Codeforces

[P3899 湖南集训] 更为厉害 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[P5904 POI2014] HOT-Hotels 加强版 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

https://www.cnblogs.com/maoyiting/p/14178833.html#/cnblog/works/article/14178833

重链剖分定义子树大小最大的为重子节点，而长链剖分定义子节点中子树 深度最大 的子节点为重子节点。如果有多个子树深度最大的子节点，取其一。如果没有子节点，就无重子节点。

性质：链的长度定义为链包含的点数

  • 任意节点 p 的 k 级祖先q所在的链的长度一定大于 k
    • 证明：分情况讨论。根据定义q→p 链的长度为 k+1 ，如果 p 和 q 在同一条链上，那这条链的长度自然大于 k 。如果p 和 q 不在同一条链上，设 q 所在链的链头和链尾分别是 top 和 tail ，根据长剖定义，top→q→tail 必须比 top→q→p 长，所以链的长度也大于 k 。
  • 任意节点 p 到根节点最多经过 n\sqrt {n} 级别的轻边
    • 证明：因为每经过一条轻边到一条新的链，新的链的长度一定严格大于上一条链（可以利用性质1简单证明），由于树上所有链的长度和为 n ，所以经过的链的长度形成一个和小于等于 n 的严格递增序列，当每次长度加1时序列最长，长度为 n 级别(1+2+3+...+n)(1+2+3+...+ \sqrt{n})。

O(1)求k级祖先P5903 【模板】树上 K 级祖先 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

  • 首先，我们同样进行一个树上倍增的预处理， O(nlog⁡n) 地预处理出每个节点的 2k2^k级祖先。然后我们再对每一个链头节点 p 预处理出它的 1,2,…,len[p]−11,2,…,len[p]−1 （ len[p] 为链长）级祖先节点和链上的1,2,…,len[p]−11,2,…,len[p]−1 级子孙节点。显然因为所有链的链长加起来是 n ，所以这部分是 O(n) 的。

  • 对于每个询问，设 $2i≤k<2i+1 $（ k=0 时特判），考虑 p 的 2i2^i 级祖先 q ，它所在的链的链长一定大于 $2^i。由于我们要找的是 q 的 $$k−2^i$级祖先，而 k−2i<2i+1−2i=2i<len[top[q]]k−2^i<2^{i+1}−2^i=2^i<len[top[q]] ，所以因为q在链上，q所在链的链头top的预处理了上下一倍链长，所以这个祖先它一定已经被预处理过了（要么在链上，要么是链头的小于链长级祖先），算一下差值，查询就好。

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
ui s;
inline ui get(ui x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return s = x;
}
void solve() {
    int n, q;
    cin >> n >> q >> s;
    int rt = 0;
    vector<int> l(n + 1), r(n + 1), node(n + 1);
    int idx = 0;
    vector<int> fa(n + 1), dep(n + 1);
    vector<int> hson(n + 1), top(n + 1), len(n + 1);
    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x == 0) {
            rt = i;
            continue;
        }
        e[x].push_back(i);
    }
    auto dfs1 = [&](auto self, int u, int curd = 1) -> void {
        dep[u] = curd;
        len[u] = 1;
        for (auto v : e[u]) {
            fa[v] = u;
            self(self, v, curd + 1);
            if (len[v] + 1 > len[u]) {
                hson[u] = v;
                len[u] = len[v] + 1;
            }
        }
    };
    auto dfs2 = [&](auto self, int u, int tp) -> void {
        l[u] = ++idx;
        node[idx] = u;
        top[u] = tp;
        if (hson[u])
            self(self, hson[u], tp);
        for (auto v : e[u]) {
            if (top[v])
                continue;
            self(self, v, v);
        }
        r[u] = idx;
    };
    int bei = __lg(n);
    vector<vector<int>> st(bei + 1, vector<int>(n + 1));
    vector<vector<int>> anc(n + 1), des(n + 1);
    auto work = [&](int rt) {
        dfs1(dfs1, rt);
        dfs2(dfs2, rt, rt);
        for (int i = 1; i <= n; i++) st[0][i] = fa[i];
        for (int i = 1; i <= bei; ++i) {
            for (int j = 1; j <= n; ++j) {
                st[i][j] = st[i - 1][st[i - 1][j]];
            }
        }
        for (int i = 1; i <= n; ++i) {
            if (top[i] == i) {
                for (int j = 0, p = i; j < len[i]; ++j, p = fa[p])
                    anc[i].push_back(p);
                for (int j = 0; j < len[i]; ++j)
                    des[i].push_back(node[l[i] + j]);
            }
        }
    };
    auto query = [&](int p, int k) {
        if (k == 0)
            return p;  // 特判
        int i = __lg(k), q = st[i][p];
        int tp = top[q];
        // q的k-(1<<i)级祖先小于链长，预处理了两倍链长的信息
        int d = k - (1 << i) - (dep[q] - dep[tp]);
        if (d > 0)
            return anc[tp][d];
        else
            return des[tp][-d];
    };
    int x, k;
    ll res = 0;
    work(rt);
    ll ans = 0;
    for (int i = 1; i <= q; i++) {
        x = (get(s) ^ res) % n + 1;
        k = (get(s) ^ res) % dep[x];
        deb(x, k);
        res = query(x, k);
        deb(res);
        ans ^= (ll)i * res;
    }
    cout << ans << endl;
}

#贪心「BZOJ 3252」攻略

给定点带权的点数为 n 的树，要选出 k条包含 叶子 的祖先后代链，使得它们并的点权和最大，每个点只能加一次。

Sol：考虑带权的长链剖分，剖出的链取前 k 条加起来即可。时间复杂度 O(nlogn)O(nlogn)。具体来说就是由于两个叶子在lca处往上只能取一次，所以我们考虑贪心取点权和最大的一条儿子链继承，贡献就加到叶子上面。答案一定是合法的，因为有叶子一定会先取叶子的，叶子的答案肯定较大。

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
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<int> ans(n + 1);
    vector<int> id(n + 1);
    function<void(int, int)> dfs = [&](int u, int fa) {
        int tmp = 0;
        for (auto v : e[u]) {
            if (v == fa)
                continue;
            dfs(v, u);
            // 必须选一个叶子节点
            if (ans[id[v]] + a[u] > tmp) {
                tmp = ans[id[v]] + a[u];
                id[u] = id[v];
            }
        }
        // 处理叶子
        if (id[u] == 0) {
            id[u] = u;
            ans[u] = a[u];
        } else
            ans[id[u]] = tmp;
    };
    dfs(1, 1);
    deb(ans);
    nth_element(ans.begin() + 1, ans.begin() + n - k + 1, ans.end());
    int res = 0;
    deb(ans);
    for (int i = n - k + 1; i <= n; i++) res += ans[i];
    cout << res << endl;
}

应用：「CF 1009F」Dominant Indices](https://codeforces.com/problemset/problem/1009/F)

题意：给定一颗1为根，n个节点的树。f(x,i)表示x子树中距离x为i的节点数f(x,i)表示x子树中距离x为i的节点数.对于每一个点求最小值k满足f(x,k)f(x,k)最大。1≤n≤1e61 \le n \le 1e6

Sol：考虑暴力dp。f[x][i]=∑y∈son[x]f[y][i−1]f[x][i]=\sum_{y \in son[x]} f[y][i-1].这种做法在一条链的时候会被卡死。考虑长链优化，先搜重儿子，利用指针偏移继承重儿子的答案。再暴力合并轻儿子的dp值，并更新答案。

  • f数组开不下，考虑指针给每个节点动态分配内存。
  • 复杂度的正确性：每个点只属于一条长链且只会在top处合并一次，实践复杂度O(n)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
int buf[M];
int *dp[N];
int *p = buf;
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<int> hson(n + 1), len(n + 1);
    function<void(int, int)> dfs = [&](int u, int fa) {
        len[u] = 1;
        for (auto v : e[u]) {
            if (v == fa)
                continue;
            dfs(v, u);
            if (len[u] < len[v] + 1) {
                hson[u] = v;
                len[u] = len[v] + 1;
            }
        }
    };
    dfs(1, 1);
    vector<int> ans(n + 1);
    function<void(int, int)> dfs2 = [&](int u, int fa) {
        dp[u][0] = 1;
        if (hson[u]) {
            dp[hson[u]] = dp[u] + 1;  // 复用重儿子，坐标偏移1
            dfs2(hson[u], u);
            ans[u] = ans[hson[u]] + 1;  // ans[u]初始化成最大深度
        }

        for (auto v : e[u]) {
            if (v == fa || v == hson[u])
                continue;
            dp[v] = p;
            p += len[v];  // 轻儿子指针动态分配内存
            dfs2(v, u);
            for (int j = 1; j <= len[v]; j++) {
                dp[u][j] += dp[v][j - 1];
                if (dp[u][j] > dp[u][ans[u]])
                    ans[u] = j;
                else if (dp[u][j] == dp[u][ans[u]] && j < ans[u]) {
                    ans[u] = j;
                }
            }
        }
        if (dp[u][ans[u]] == 1)
            ans[u] = 0;
    };
    dp[1] = p;
    p += len[1];
    dfs2(1, 1);
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;
}

一道简单的树形dp，从叶子向上传递信息https://www.luogu.com.cn/problem/CF767C

题意：一棵树点权有正有负，找到两个边去除以后，树被分成三部分，三部分的点权和相等。输出一组方案。不存在输出-1

Sol：赛时做法：割两个边要输出u->v的v表示方案，记录为v1,v2。首先总和必须整除3。考虑在lca处可以统计到答案，是一个先更新答案，再合并子树的过程，所以需要保留信息向上传递。

再考虑每次把当前子树根节点合并进去的时候，会重复计算贡献，也就是为祖先关系的时候应该当前子树根是2sum3\frac{2 sum}{3}并且子树内部存在sum3\frac{sum}{3},从这可以看出为什么要特判0.

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
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> e(n + 1);
    int rt;
    vector<int> a(n + 1);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x >> a[i], sum += a[i];
        if (x == 0)
            rt = i;
        else
            e[x].push_back(i);
    }
    if (sum % 3) {
        cout << -1 << endl;
        return;
    }
    int tar = sum / 3;
    deb(tar);
    vector<int> f1(n + 1);
    vector<int> mp(n + 1);
    // pii ans;
    vector<int> c;
    function<void(int)> dfs = [&](int u) {
        for (auto v : e[u]) {
            deb(u, v, a[u]);
            dfs(v);
            // 更新答案
            if (f1[v] && f1[u]) {  // 两个割点的lca处统计
                cout << mp[u] << " " << mp[v] << endl;
                exit(0);
            }
            //   if (a[v] == tar)这是错的，下面的答案传递不上来
            //     mp[u] = mp[v];
            // 更新数组
            if (f1[v])
                mp[u] = mp[v];
            f1[u] += f1[v];
            a[u] += a[v];
        }
        if (u != rt) {       // 根节点不能贡献
            if (tar == 0) {  // 这需要特殊判断
                if (a[u] == tar && f1[u] >= 1) {
                    cout << u << " " << mp[u] << endl;
                    exit(0);
                }
                if (a[u] == tar) {
                    f1[u] += 1, mp[u] = u;
                }
            } else {  // 两个割点成祖先关系
                if (a[u] == tar)
                    f1[u] += 1, mp[u] = u;
                if (a[u] == 2 * tar && f1[u]) {
                    cout << u << " " << mp[u] << endl;
                    exit(0);
                }
            }
        }
    };
    dfs(rt);
    deb(a);
    cout << -1 << endl;
}

反思一种简明的写法：考虑找到合法点就一定割是对的。为了不重复计算直接dp值合法点的减去一次，不可能存在超过两个这样的点，不然就说明有好几个部分相加等于sum。除非sum为0，而sum为0，在我们减去贡献是不影响的。

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
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> e(n + 1);
    int rt=0;
    vector<int> a(n + 1);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x >> a[i], sum += a[i];
        if (x == 0)
            rt = i;
        else
            e[x].push_back(i);
    }
    if (sum % 3) {
        cout << -1 << endl;
        return;
    }
    int tar = sum / 3;
    int v1 = 0, v2 = 0;
    auto dfs = [&](auto self, int u) -> void {
        for (auto v : e[u]) {
            self(self, v);
            a[u] += a[v];
            if (a[v] == tar) {
                if (v1 == 0) {
                    v1 = v;
                    a[u] -= a[v];
                } else if (v2 == 0) {
                    v2 = v;
                    a[u] -= a[v];
                }
            }
        }
    };
    dfs(dfs, rt);
    if (v1 && v2)
        cout << v1 << " " << v2 << endl;
    else
        cout << -1 << endl;
}