heavy light decomposition / 重軽分解
(old/heavy_light_decomposition.inc.cpp)

• View this file on GitHub
• Last update: 2020-01-08 18:35:19+09:00
• Link: http://math314.hateblo.jp/entry/2014/06/24/220107

Code

/**
 * @brief heavy light decomposition / 重軽分解
 * @description for given rooted tree $G = (V, E)$, decompose the vertices to disjoint paths, and construct new small rooted tree $G' = (V', E')$ of the disjoint paths.
 * @see http://math314.hateblo.jp/entry/2014/06/24/220107
 */
struct heavy_light_decomposition {
    vector<vector<int> > path; // : V' -> list of V, bottom to top order
    vector<int> path_of; // : V -> V'
    vector<int> index_of; // : V -> int, the index of the vertex in the path that belongs to
    vector<int> parent; // : V' -> V, one node has -1 as the parent
    heavy_light_decomposition(int root, vector<vector<int> > const & g) {
        int n = g.size();
        vector<int> tour_parent(n, -1);
        vector<int> euler_tour(n); {
            int i = 0;
            stack<int> stk;
            tour_parent[root] = -1;
            euler_tour[i ++] = root;
            stk.push(root);
            while (not stk.empty()) {
                int x = stk.top(); stk.pop();
                for (int y : g[x]) if (y != tour_parent[x]) {
                    tour_parent[y] = x;
                    euler_tour[i ++] = y;
                    stk.push(y);
                }
            }
        }
        path_of.resize(n);
        index_of.resize(n);
        vector<int> subtree_height(n);
        int path_count = 0;
        REP_R (i, n) {
            int y = euler_tour[i];
            if (y != root) {
                int x = tour_parent[y];
                chmax(subtree_height[x], subtree_height[y] + 1);
            }
            if (subtree_height[y] == 0) {
                // make a new path
                path_of[y] = path_count ++;
                index_of[y] = 0;
                path.emplace_back();
                path.back().push_back(y);
                parent.push_back(tour_parent[y]);
            } else {
                // add to an existing path
                int i = -1;
                for (int z : g[y]) {
                    if (subtree_height[z] == subtree_height[y] - 1) {
                        i = path_of[z];
                        break;
                    }
                }
                assert (i != -1);
                path_of[y] = i;
                index_of[y] = path[i].size();
                path[i].push_back(y);
                parent[i] = tour_parent[y];
            }
        }
    }

    /**
     * @brief construct an adjacency list for the decomposed tree
     * @note undircted
     */
    vector<vector<int> > to_adjacency_list() const {
        int n = path.size();
        vector<vector<int> > g(n);
        REP (i, n) {
            if (parent[i] == -1) continue;
            int j = path_of[parent[i]];
            g[i].push_back(j);
            g[j].push_back(i);
        }
        return g;
    }

    /**
     * @brief reduce a path-query to range-queries aboud nodes
     * @arg lca is for the original tree, not the decomposed tree
     * @arg func is a callback function f(i, l, r), where i in V is an index of path, [l, r) is a range on the path
     */
    template <class LowestCommonAncestor, class Func>
    void path_node_do_something(LowestCommonAncestor const & lca, int x, int y, Func func) const {
        int z = lca(x, y);
        auto climb = [&](int & v) {
            while (path_of[v] != path_of[z]) {
                int i = path_of[v];
                func(i, index_of[v], path[i].size());
                v = parent[i];
            }
        };
        climb(x);
        climb(y);
        int i = path_of[z];
        if (index_of[x] > index_of[y]) swap(x, y);
        func(i, index_of[x], index_of[y] + 1);
    }
};


template <typename SegmentTree>
struct heavy_light_decomposition_edge_adapter {
    typedef typename SegmentTree::monoid_type CommutativeMonoid;
    typedef typename SegmentTree::endomorphism_type Endomorphism;
    typedef typename CommutativeMonoid::type type;

    vector<SegmentTree> segtree;
    vector<type> link; // edges between a segtree and the parent segtree
    heavy_light_decomposition & hl;
    lowest_common_ancestor & lca;
    CommutativeMonoid mon;
    Endomorphism endo;
    heavy_light_decomposition_edge_adapter(
            heavy_light_decomposition & a_hl,
            lowest_common_ancestor & a_lca,
            type initial_value = CommutativeMonoid().unit(),
            CommutativeMonoid const & a_mon = CommutativeMonoid(),
            Endomorphism const & a_endo = Endomorphism())
            : hl(a_hl), lca(a_lca), mon(a_mon), endo(a_endo) {
        repeat (i, hl.path.size()) {
            segtree.emplace_back(hl.path[i].size()-1, initial_value, a_mon, a_endo);
        }
        link.resize(hl.path.size(), initial_value);
    }

    template <class Func1, class Func2>
    void path_do_something(int x, int y, Func1 func1, Func2 func2) {
        int z = lca(x, y);
        auto climb = [&](int & x) {
            while (hl.path_of[x] != hl.path_of[z]) {
                int i = hl.path_of[x];
                func1(segtree[i], hl.index_of[x], hl.path[i].size()-1);
                func2(link[i]);
                x = hl.parent[i];
            }
        };
        climb(x);
        climb(y);
        int i = hl.path_of[z];
        if (hl.index_of[x] > hl.index_of[y]) swap(x, y);
        func1(segtree[i], hl.index_of[x], hl.index_of[y]);
    }
    type path_concat(int x, int y) {
        type acc = mon.unit();
        path_do_something(x, y, [&](SegmentTree & segtree, int l, int r) {
            acc = mon.append(acc, segtree.range_concat(l, r));
        }, [&](type & value) {
            acc = mon.append(acc, value);
        });
        return acc;
    }
    void path_apply(int x, int y, typename Endomorphism::type f) {
        path_do_something(x, y, [&](SegmentTree & segtree, int l, int r) {
            segtree.range_apply(l, r, f);
        }, [&](type & value) {
            value = endo.apply(f, value);
        });
    }
};

#line 1 "old/heavy_light_decomposition.inc.cpp"
/**
 * @brief heavy light decomposition / 重軽分解
 * @description for given rooted tree $G = (V, E)$, decompose the vertices to disjoint paths, and construct new small rooted tree $G' = (V', E')$ of the disjoint paths.
 * @see http://math314.hateblo.jp/entry/2014/06/24/220107
 */
struct heavy_light_decomposition {
    vector<vector<int> > path; // : V' -> list of V, bottom to top order
    vector<int> path_of; // : V -> V'
    vector<int> index_of; // : V -> int, the index of the vertex in the path that belongs to
    vector<int> parent; // : V' -> V, one node has -1 as the parent
    heavy_light_decomposition(int root, vector<vector<int> > const & g) {
        int n = g.size();
        vector<int> tour_parent(n, -1);
        vector<int> euler_tour(n); {
            int i = 0;
            stack<int> stk;
            tour_parent[root] = -1;
            euler_tour[i ++] = root;
            stk.push(root);
            while (not stk.empty()) {
                int x = stk.top(); stk.pop();
                for (int y : g[x]) if (y != tour_parent[x]) {
                    tour_parent[y] = x;
                    euler_tour[i ++] = y;
                    stk.push(y);
                }
            }
        }
        path_of.resize(n);
        index_of.resize(n);
        vector<int> subtree_height(n);
        int path_count = 0;
        REP_R (i, n) {
            int y = euler_tour[i];
            if (y != root) {
                int x = tour_parent[y];
                chmax(subtree_height[x], subtree_height[y] + 1);
            }
            if (subtree_height[y] == 0) {
                // make a new path
                path_of[y] = path_count ++;
                index_of[y] = 0;
                path.emplace_back();
                path.back().push_back(y);
                parent.push_back(tour_parent[y]);
            } else {
                // add to an existing path
                int i = -1;
                for (int z : g[y]) {
                    if (subtree_height[z] == subtree_height[y] - 1) {
                        i = path_of[z];
                        break;
                    }
                }
                assert (i != -1);
                path_of[y] = i;
                index_of[y] = path[i].size();
                path[i].push_back(y);
                parent[i] = tour_parent[y];
            }
        }
    }

    /**
     * @brief construct an adjacency list for the decomposed tree
     * @note undircted
     */
    vector<vector<int> > to_adjacency_list() const {
        int n = path.size();
        vector<vector<int> > g(n);
        REP (i, n) {
            if (parent[i] == -1) continue;
            int j = path_of[parent[i]];
            g[i].push_back(j);
            g[j].push_back(i);
        }
        return g;
    }

    /**
     * @brief reduce a path-query to range-queries aboud nodes
     * @arg lca is for the original tree, not the decomposed tree
     * @arg func is a callback function f(i, l, r), where i in V is an index of path, [l, r) is a range on the path
     */
    template <class LowestCommonAncestor, class Func>
    void path_node_do_something(LowestCommonAncestor const & lca, int x, int y, Func func) const {
        int z = lca(x, y);
        auto climb = [&](int & v) {
            while (path_of[v] != path_of[z]) {
                int i = path_of[v];
                func(i, index_of[v], path[i].size());
                v = parent[i];
            }
        };
        climb(x);
        climb(y);
        int i = path_of[z];
        if (index_of[x] > index_of[y]) swap(x, y);
        func(i, index_of[x], index_of[y] + 1);
    }
};


template <typename SegmentTree>
struct heavy_light_decomposition_edge_adapter {
    typedef typename SegmentTree::monoid_type CommutativeMonoid;
    typedef typename SegmentTree::endomorphism_type Endomorphism;
    typedef typename CommutativeMonoid::type type;

    vector<SegmentTree> segtree;
    vector<type> link; // edges between a segtree and the parent segtree
    heavy_light_decomposition & hl;
    lowest_common_ancestor & lca;
    CommutativeMonoid mon;
    Endomorphism endo;
    heavy_light_decomposition_edge_adapter(
            heavy_light_decomposition & a_hl,
            lowest_common_ancestor & a_lca,
            type initial_value = CommutativeMonoid().unit(),
            CommutativeMonoid const & a_mon = CommutativeMonoid(),
            Endomorphism const & a_endo = Endomorphism())
            : hl(a_hl), lca(a_lca), mon(a_mon), endo(a_endo) {
        repeat (i, hl.path.size()) {
            segtree.emplace_back(hl.path[i].size()-1, initial_value, a_mon, a_endo);
        }
        link.resize(hl.path.size(), initial_value);
    }

    template <class Func1, class Func2>
    void path_do_something(int x, int y, Func1 func1, Func2 func2) {
        int z = lca(x, y);
        auto climb = [&](int & x) {
            while (hl.path_of[x] != hl.path_of[z]) {
                int i = hl.path_of[x];
                func1(segtree[i], hl.index_of[x], hl.path[i].size()-1);
                func2(link[i]);
                x = hl.parent[i];
            }
        };
        climb(x);
        climb(y);
        int i = hl.path_of[z];
        if (hl.index_of[x] > hl.index_of[y]) swap(x, y);
        func1(segtree[i], hl.index_of[x], hl.index_of[y]);
    }
    type path_concat(int x, int y) {
        type acc = mon.unit();
        path_do_something(x, y, [&](SegmentTree & segtree, int l, int r) {
            acc = mon.append(acc, segtree.range_concat(l, r));
        }, [&](type & value) {
            acc = mon.append(acc, value);
        });
        return acc;
    }
    void path_apply(int x, int y, typename Endomorphism::type f) {
        path_do_something(x, y, [&](SegmentTree & segtree, int l, int r) {
            segtree.range_apply(l, r, f);
        }, [&](type & value) {
            value = endo.apply(f, value);
        });
    }
};

Back to top page