算法学习笔记:长链剖分

引例

CF1009F Dominant Indices

给定一棵$n$个点的树,令$f(u,i)$表示$u$的子树中到$u$距离为$i$的点的个数,对于每个点$u$,求使$f(u,i)$最大的$i$。若有多个,输出最小的一个。$n\le 10^6$。

思路

考虑朴素解法,对于$u$的每个儿子$v$,枚举深度$i$,用$f(v,i)$更新$f(u,i+1)$。

定义子树高度$d(u)$表示$u$子树中的点到$u$的最大距离,则合并每个儿子的复杂度是$O(d(v))$的。直接做的复杂度是$O(n^2)$。

可以发现$d(v) \le size(v)$,如果我们把$d(v)$看作$size(v)$,就可以利用树上启发式合并的思想,把复杂度优化到$O(n\log n)$。

具体地,用重链剖分预处理出每个点$u$的重儿子$son(u)$($size$最大的儿子),在合并$u$所有儿子的$f$数组时,先继承$u$重儿子的数组,再暴力合并其它儿子。

合并点$v$的复杂度是$O(size(v))$,相当于$v$子树中每个点有$1$的贡献,而每个点最多会被暴力合并$\log$次,产生$\log$的贡献,所以总复杂度为$O(n\log n)$。

注意到这是我们把$d(v)$看作$size(v)$的结果,而实际上$d(v)$是更小的,考虑能不能继续优化。

长链剖分

树链剖分其实分为两种:上面用的按$size(v)$划分重儿子的方法称为重链剖分,而另一种长链剖分是按$d(v)$划分重儿子。我们把所有连接重儿子的边连起来,就可以把树划分成一条条长链。

(其实应该叫长儿子?然而不顺口。)

更改了划分重儿子的方法后,我们同样使用上述算法,继承重儿子的信息,然后暴力合并轻儿子。

不同的是,之前合并$v$的复杂度是$size(v)$,而现在是$d(v)$。之前我们看作$v$子树中的每个点对复杂度产生$1$的贡献,而现在是$v$所在的长链上每个点产生$1$的贡献。可以发现,每条长链只会被暴力合并一次(从链顶合并到链顶的父亲),那么总复杂度就是$O(n)$的。

可以发现,长链剖分也适用于其它子树合并复杂度为$O(\sum d(v))$的问题,比如一些与深度有关的dp。

代码

用指针的方式实现$f$数组的继承,空间复杂度也是$O(n)$的。

#include <bits/stdc++.h>

const int N = 1e6+50;

struct Graph {
    struct Edge {
        int to, nxt;
    } e[N<<1];
    int top, head[N];

    Graph(): top(0) {
        memset(head, -1, sizeof head);
    }

    void add(int u, int v) {
        e[top] = (Edge){v, head[u]};
        head[u] = top++;
    }

    void add2(int u, int v) {
        add(u, v);
        add(v, u);
    }
} G;

int n;
int tmp[N], *f[N], *cur = tmp;
int son[N], len[N];
int ans[N];

void dfs(int u, int fa) {
    for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
        int v = G.e[i].to;
        if (v == fa) continue;
        dfs(v, u);
        if (!son[u] || len[v] > len[son[u]])
            son[u] = v;
    }
    len[u] = len[son[u]] + 1;
}

void dp(int u, int fa) {
    f[u][0] = 1;
    ans[u] = 0; 
    if (son[u]) {
        f[son[u]] = f[u] + 1;
        dp(son[u], u);
        if (f[son[u]][ans[son[u]]] > 1)
            ans[u] = ans[son[u]] + 1;
    }
    for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
        int v = G.e[i].to;
        if (v == fa || v == son[u]) continue;
        f[v] = cur;
        cur += len[v];
        dp(v, u);
        for (int j = 1; j <= len[v]; j++) {
            f[u][j] += f[v][j-1];
            if (f[u][j] > f[u][ans[u]] || (f[u][j] == f[u][ans[u]] && j < ans[u]))
                ans[u] = j;
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        G.add2(u, v);
    }
    dfs(1, 0);
    f[1] = cur;
    cur += len[1];
    dp(1, 0);
    for (int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
    return 0;
}

拓展应用:$O(n\log n)-O(1)$求$k$级祖先

长链剖分之O(nlgn)-O(1)求k级祖先 - 知乎

这篇写得很清楚,就不再复述。



转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论