ホーム > libalgo

木の平方分割

概要

木を大きさ高々 $B$ の部分木に分解し,$O(\frac{N}{B})$ の木からなる森を作る.こうすると $O(N)$ のクエリが $O(\frac{N}{B} + B)$ で処理できることがある. 分解するには,根から BFS をして最初のブロックをとり,別れた森のそれぞれの根から BFS をして… を繰り返す.下の例は LCA をクエリあたり $O(\sqrt N)$ で処理する例.

計算量

構築 $O(N)$.クエリあたり $O(\sqrt N)$.

計算量

tree_sqrt_decomp tree(N)
大きさ N の辺なしグラフを作る
tree.add_edge(u,v)
無向辺 (u, v) を追加する
tree.decomp(root, B)
root を根として大きさ B の木に分割する
tree.lca(u,v)
u と v の LCA を求める
tree.parent[v]
v の親
tree.color[v]
v が属するブロック
tree.go_up[v]
v が属するブロックの根の親
tree.root_depth[v]
v が属するブロックの根の深さ

実装

const int B = 512;

struct sqrt_decomp_tree {
    int n;
    int size() const { return n; }
    std::vector<int> color, parent, depth, root_depth, go_up, visited;
    std::vector<std::vector<int>> g;
    sqrt_decomp_tree(int n_) : n(n_), g(n) {}
    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void decomp(int root = 0) {
        parent.assign(n, -1);
        depth.assign(n, 0);
        root_depth.assign(n, 0);
        go_up.assign(n, -1);
        visited.assign(n, false);
        std::vector<int> tord;
        std::vector<int> q(n + 1);
        int l = 0, r = 0;
        q[r++] = root;
        while (l != r) {
            int v = q[l++];
            visited[v] = true;
            tord.push_back(v);
            for (int c : g[v]) {
                if (!visited[c]) {
                    parent[c] = v;
                    depth[c] = depth[v] + 1;
                    q[r++] = c;
                }
            }
        }
        std::swap(color, visited);  // メモリをケチる
        color.assign(n, -1);
        int c = 0;
        for (int u : tord) {
            if (color[u] != -1) continue;
            l = 0, r = 0;
            q[r++] = u;
            for (int i = 0; i < B && l != r; i++) {
                int v = q[l++];
                color[v] = c;
                go_up[v] = parent[u];
                root_depth[v] = depth[u];
                for (int c : g[v])
                    if (color[c] == -1) q[r++] = c;
            }
            c++;
        }
    }
    int lca(int u, int v) {
        while (root_depth[u] > root_depth[v]) u = go_up[u];
        while (root_depth[u] < root_depth[v]) v = go_up[v];
        while (depth[u] > depth[v]) u = parent[u];
        while (depth[u] < depth[v]) v = parent[v];
        while (u != v) u = parent[u], v = parent[v];
        return u;
    }
};

検証

AOJ GRL5C (Submission)

参考文献

完全制覇・ツリー上でのクエリ処理技法 - (iwi) { 反省します - TopCoder部