树上启发式合并

泛化

启发式合并可以被归类为“用脑子优化”。

比如常见的并查集按秩合并，就是一种启发式合并：

bool Merge(int u, int v) {
    int ru = root(u), rv = root(v);
    if(ru == rv) return false;
    if(siz[ru] > siz[rv]) pa[rv] = ru, siz[ru] += siz[rv];
    else pa[ru] = rv, siz[rv] += siz[ru];
    return true;
}

通常来说我们不能感性的去证明这类优化的复杂度，我们需要理性的分析。

比如并查集按秩合并，虽然但是，我并不会证明这个东西的复杂度，但是可以看一下论文：Tarjan, R. E., & Van Leeuwen, J. (1984). Worst-case analysis of set union algorithms. Journal of the ACM (JACM), 31(2), 245-281。

但这类问题的思想都是大同小异的，通过安排某种特定的合并顺序，使得合并的基本操作数/复杂度能够减少。

对于 dsu on tree（称作树上启发式合并应当更恰当），通常我们所遇到的是一类静态的查询子树信息的问题。

对于暴力做法，我们需要直接遍历所有子树考虑求出答案，也不做任何继承，复杂度是 \(O(n^2)\) 的。（假定一次合并为 \(O(1)\)。）

我们注意到做继承实际上很麻烦，为了节省空间，我们一般使用的是一个全局数组统计答案，递归下去很不好计算这个全局数组的变化。

而我们不妨考虑一个优化，我们先把所有轻儿子的答案算出来，但是对于当前节点的贡献我们并不保留。

然后我们递归下去算重儿子的贡献，并保留它对全局数组的影响，然后再加入轻儿子的影响，这看起来和原来没什么差别。

但实际上，重儿子的影响被直接继承了，而我们暴力合并的都是轻儿子的影响，我们不妨分析一些这个过程。

从重链剖分那里我们能知道，任意一个节点到根节点的轻边级别为 \(O(\log n)\)，具体来说设这个点子树大小为 \(siz\)，经过了 \(l\) 条轻边。

因为轻边连接的子树不会超过子树的一半，所以每过一个轻边子树就会折半，那么 \(siz \le n / 2^l\)，所以 \(l\) 的级别是 \(\log n\) 的。

然后，因为我们合并的时候跳过了重儿子，所以每个节点的被访问次数就是 \(l + 1\)，那么每个节点均摊会被访问 \(\log n\) 次。

总复杂度就变成了 \(O(n \log n)\)。

例题

子树数颜色个数

题面就这么简单，没啥好说的，可以在这里交。

做法就是我们上面所提到的，维护一个全局 cnt 数组即可，然后因为我们实际上做了一个重链剖分，所以加入整个子树不用递归直接 dfn 扫一下就好，常数会小一点。

dfs 可以记录一个变量表示当前是否保留，就不用多写 dfs 了。

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\)。

暴力做法就是直接一个形如树上背包的东西。

然后我们还是考虑 dsu on tree 优化，重儿子直接用，轻儿子再做一次 dp 暴力加。

Code

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.
}

---

最后更新: October 23, 2023