跳转至

Dsu on tree old

概述ψ(｀∇´)ψ

全称树上启发式合并，也叫优雅的树上暴力。

这东西听说实际上是一种静态链分治。

但是无所谓，能拿来做题就行。

启发式算法的思想就是，用你的脑子和直觉去优化一些算法过程。

一个比较常见的例子就是并查集的按秩合并，也算是一种启发式合并：

1
2
3
4
5
6
7
8
void Union(int x, int y) {
    int rx = root(x), ry = root(y);
    if(rx == rx) return;
    if(siz[rx] < siz[ry]) 
        pa[rx] = ry, siz[ry] += siz[rx];
    else 
        pa[ry] = rx, siz[rx] += siz[ry];
}

这里把小的集合的接到大的集合下面，原因是集合的大小可以近似的看作集合的高度。

把高度矮的合并到高度高的显然能更快的进行找集合父亲的操作 root()。

树上启发式合并其实和这个比较类似，也是利用启发式算法的思想，来优化树上子节点信息的合并过程。

这可能也是这个算法叫 dsu on tree 的原因。

应用ψ(｀∇´)ψ

泛化ψ(｀∇´)ψ

dsu on tree 主要运用于一类树上问题，这类问题一般需要通过儿子子树的信息“合并”来得到父亲子树的信息。

这里的合并可以简单的理解为：“把所有儿子对应的答案直接通过某种方式揉到一起”

如果是在线，且每个节点维护的信息是一个值域或者序列时，可以考虑使用线段树合并。

如果是离线，就可以考虑使用 dsu on tree 来对暴力合并进行优化

在多数时候速度能吊打树上莫队，树套树等难写的算法。

例题ψ(｀∇´)ψ

Last mile of the way

给定你一棵树，每一个节点有一个权值 \(w\) 和一个体积 \(a\)。

有 \(q\) 次询问，每次询问形如 \(x, s\)，

表示询问在以 \(x\) 为根的子树中，选不超过 \(s\) 的节点，权值和的最大值。

这里没有任何依赖关系，相当于把这个子树里的所有节点提出来当成一个序列来取。

\(1\le n \le 5\times 10^3, q\le 10^5, w_i \le 10^6, a,x,s \le 5\times 10^3\)。

首先这题可以考虑直接用 dfs 序的性质，把每一个子树直接化成一个序列上的区间。

然后就可以直接莫队，但感觉复杂度不太行（本质上是树上莫队）。

有没有更好的算法？

先考虑一个朴素的 \(30pts\) 算法：本题相当于一个去掉依赖限制的树上背包。

所以我们可以仿照树上背包的方程：设 \(dp_{u, i}\) 表示以 \(u\) 为根的子树中，选不超过 \(i\) 的空间的所有方案，属性为权值和最大值。

然后可以对集合进行一个划分：一半是选 \(u\)，一半是不选 \(u\)。

考虑对这两个部分各自转移，但实际上除了选/不选 \(u\) 的决策以外，他们的决策转移方式是相同的。

发现转移只需要枚举分配给 \(u\) 所有的儿子以及以它们为根的子树的空间 \(j\)，

然后对于每个儿子枚举一个 \(k_v\)，表示这个儿子 \(v\) 以及它的子树分到的空间。

对于每个 \(j\)，合法的转移状态是一组满足 \(\sum_v k_v = j\) 的 \(k\)。

这个 \(\sum_v k_v = j\) 怎么满足呢？ 其实我们只需要关心当前扫描到的儿子分配了多少空间即可，因为我们并不关心当前答案是怎么来的。

所以两重循环就可以了。

还需要记得考虑 \(u\) 选或者不选，因为这里没有强制选 \(u\) 了，所以和有依赖的背包不太一样。

可以写出一个暴力代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs(int u, int fa) {
    for(int i = head[u]; ~i; i = e[i].Next) {
        int v = e[i].ver;
        if(v == fa) continue;
        dfs(v, u);
    }
    for(int i = head[u]; ~i; i = e[i].Next) {
        int v = e[i].ver;
        if(v == fa) continue;
        for(int j = m; j >= a[u]; --j) {
            // 因为这是一个分组背包的过程，要保证每个物品只选一次，就要倒序循环。
            for(int k = j; k >= 0; --k) {
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
            }
        }
    }
    // 到这里，dp 数组还是没有考虑 u 的决策的，所以还要循环搞一次。
    for(int i = m; i >= a[u]; --i) 
        dp[u][i] = max(dp[u][i], dp[u][i - a[u]] + w[u]);
    // 因为不是强制选，所以就直接取 max 即可。
}

我们仔细分析一下这个过程。

可以发现，在转移一组合法的 \(j\) 的时候，我们实际上是把满足 \(\sum_v k_v = j\) 的一组 \(k\) 合并起来得到 \(dp_{u,j}\) 这个状态。

也就是把所有儿子的状态全部暴力合并起来，所以此时我们可以考虑一个优化。

类似树链剖分，设节点 \(u\) 的重儿子 \(hson_u\) 为 \(siz_v\) 最大的一个儿子 \(v\)。

转移的时候我们直接把重儿子的 \(dp\) 值序列 \(dp_{hson_u}\) 拿过来用。

也就是让 \(u\) 直接继承重儿子的答案。

然后我们暴力把所有轻儿子的子树的答案直接合并到 \(u\) 上，最后再把考虑 \(u\) 的答案算上。

实际上这就是把 \(u\) 自己当作一个单独的轻儿子节点然后进行暴力合并。

所以合并 \(u\) 的答案和合并轻儿子答案的方式应当是一样的。

我们都直接暴力决策对应的节点选或者不选，只是轻儿子需要递归下去继续暴力取。

可以证明这样做之后，对于每个点的复杂度是 \(\text{O}(n \log n)\) 的。

也就是通过启发式合并的思想把 \(\text{O}(n^2)\) 暴力合并优化到了 \(\text{O}(n \log n)\)。

具体实现看代码：

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
int siz[si];
int hson[si]; // u 的重儿子
i64 dp[si][si], ans[si][si];

// 预处理重儿子
void dfs1(int u, int fa) {
    int kot = 0;
    siz[u] = 1, hson[u] = 0;

    for(int i = head[u]; ~i; i = e[i].Next) {
        int v = e[i].ver;
        if(v == fa) continue;
        dfs1(v, u), siz[u] += siz[v];
        if(siz[v] > kot) 
            kot = siz[v], hson[u] = v;
    } 
}
// 暴力加以 u 为根的子树当中的所有物品
void dfs2(int u, int fa, i64 *f) {
    for(int i = m; i >= a[u]; --i) 
        f[i] = max(f[i], f[i - a[u]] + w[u]);

    for(int i = head[u]; ~i; i = e[i].Next) {
        int v = e[i].ver;
        if(v == fa) continue;
        // 这里是暴力加就不要判重儿子了（实测会WA）
        dfs2(v, u, f);
    }
}
// dp 的过程
void dfs3(int u, int fa) {
    for(int i = head[u]; ~i; i = e[i].Next) {
        int v = e[i].ver;
        if(v == fa) continue;
        dfs3(v, u);
    }

    memcpy(dp[u], dp[hson[u]], sizeof dp[u]);
    for(int i = head[u]; ~i; i = e[i].Next) {
        int v = e[i].ver;
        if(v == fa || v == hson[u]) continue;
        dfs2(v, u, dp[u]);
    }
    for(int i = m; i >= a[u]; --i) {
        dp[u][i] = max(dp[u][i], dp[u][i - a[u]] + w[u]);
    }

    // i64 *kot = dp[hson[u]]; // 直接继承重儿子
    // for(int i = head[u]; ~i; i = e[i].Next) {
    //  int v = e[i].ver;
    //  if(v == fa || v == hson[u]) continue;
    //  dfs2(v, u, kot);
    // }

    // for(int i = m; i >= a[u]; --i) 
    //  kot[i] = max(kot[i], kot[i - a[u]] + w[u]);
    // for(int i = 0; i <= m; ++i) 
    //  ans[u][i] = kot[i];
    // 因为是离线且自底向上更新，所以不用考虑直接用重儿子的数组修改后会影响答案。
    // memcpy 虽然很快，但是复杂度不对，但是这个指针写法似乎有问题？ 

    // TODO : fix it.
}

复杂度证明可以看看 OI-wiki，之后再补。

总结ψ(｀∇´)ψ

总结一下，dsu on tree 其实就是对于需要合并信息的一类离线树上问题，利用启发式合并的思想优化。

过程大致如下：

  1. 直接让 \(u\) 的信息数组继承 \(hson_u\) 的信息数组。
  2. 暴力把其它轻儿子的信息合并到 \(u\) 的信息数组上。 这里合并的方式因题而异。
  3. 最后把考虑 \(u\) 的情况合并上去即可。
最后更新: October 23, 2023