HL分解(辺クエリ)
(tree/hld_edge.cpp)

View this file on GitHub
Last update: 2026-03-13 21:29:59+09:00

説明

辺を子頂点側の位置に載せる重軽分解である。根の位置には辺がないので、edge_index(root) は -1 を返す。パスクエリ・パス更新は $O(log^2 N)$。

できること

HeavyLightDecompositionEdge hld(n) 頂点数 n の木を作る
void add_edge(int u, int v) 木辺を張る
void build(vector<int> roots = {0}) 前処理をする。森にも対応する
int edge_index(int v) parent(v) - v の辺が載る位置を返す。根なら -1
pair<int, int> subtree(int v) 部分木の辺集合に対応する半開区間 [l, r) を返す
void path(int u, int v, F f) u - v パス上の辺を被覆する各区間へ f(l, r) を呼ぶ
T path_query(int u, int v, T e, Q q, F f) 可換向け辺パスクエリ
T path_query_ordered(int u, int v, T e, QL ql, QR qr, F f) 非可換向け順序付き辺パスクエリ
void apply_subtree(int v, F f) 部分木の辺区間へ f(l, r) を呼ぶ
T subtree_query(int v, Q q) 部分木の辺区間クエリ

使い方

各辺の値は子頂点側に置く。 parent(v) - v の辺を更新したいときは edge_index(v) を使う。パス順序が必要なときは path_query_ordered を使う。

HeavyLightDecompositionEdge hld(n);
hld.add_edge(u, v);
hld.build();

int p = hld.edge_index(v);
seg.update(p, x);

auto ans = hld.path_query_ordered(a, b, Monoid::e(), ql, qr, Monoid::f);

実装上の補足

内部では頂点版 HLD の edge = true を使っている。 subtree(v) は v 自身へ入る辺を含まないので、根の部分木では木全体の辺区間になる。

Depends on

HL分解(HL Decomposition) (tree/hld.cpp)

Verified with

test/yuki650_hld_edge.test.cpp

Code

#include "hld.cpp"

struct HeavyLightDecompositionEdge {
    HeavyLightDecomposition hld;

    explicit HeavyLightDecompositionEdge(int n) : hld(n) {}
    explicit HeavyLightDecompositionEdge(vector<vector<int>> &g) : hld(g) {}

    void add_edge(int u, int v) {
        hld.add_edge(u, v);
    }

    void build(vector<int> roots = {0}) {
        hld.build(roots);
    }

    int lca(int u, int v) {
        return hld.lca(u, v);
    }

    int parent(int v) const {
        return hld.parent(v);
    }

    int ancestor(int v, int k) {
        return hld.ancestor(v, k);
    }

    int distance(int u, int v) {
        return hld.distance(u, v);
    }

    int edge_index(int v) const {
        if (hld.par[v] == -1) return -1;
        return hld.id[v];
    }

    pair<int, int> subtree(int v) const {
        return hld.subtree(v, true);
    }

    template<typename F>
    void path(int u, int v, const F &f) {
        hld.path(u, v, f, true);
    }

    template<typename F>
    void apply_subtree(int v, const F &f) {
        hld.apply_subtree(v, f, true);
    }

    template<typename T, typename Q, typename F>
    T path_query(int u, int v, const T &e, const Q &q, const F &f) {
        return hld.path_query(u, v, e, q, f, true);
    }

    template<typename T, typename QL, typename QR, typename F>
    T path_query_ordered(int u, int v, const T &e, const QL &ql, const QR &qr, const F &f) {
        return hld.path_query_ordered(u, v, e, ql, qr, f, true);
    }

    template<typename T, typename Q>
    T subtree_query(int v, const Q &q) {
        return hld.subtree_query<T>(v, q, true);
    }
};

/**
 * @brief HL分解(辺クエリ)
 */

#line 1 "tree/hld.cpp"

class HeavyLightDecomposition {
    void dfs_sz(int v){
        int heavy = -1;
        for (auto &&u : G[v]) {
            if(u == par[v]) continue;
            par[u] = v; dep[u] = dep[v] + 1;
            dfs_sz(u);
            sub_size[v] += sub_size[u];
            if(heavy == -1 || sub_size[u] > sub_size[heavy]) heavy = u;
        }
        if (heavy != -1 && G[v][0] != heavy) {
            for (auto &&u : G[v]) {
                if (u == heavy) {
                    swap(u, G[v][0]);
                    break;
                }
            }
        }
    }
    void dfs_hld(int v, int c, int &pos){
        id[v] = pos++;
        id_inv[id[v]]= v;
        tree_id[v] = c;
        for (auto &&u : G[v]) {
            if(u == par[v]) continue;
            head[u] = (u == G[v][0] ? head[v] : u);
            dfs_hld(u, c, pos);
        }
    }
public:
    int n;
    vector<vector<int>> G;
    vector<int> par, dep, sub_size, id, id_inv, tree_id, head;
    explicit HeavyLightDecomposition(int n) : n(n), G(n), par(n), dep(n), sub_size(n, 1), id(n), id_inv(n), tree_id(n), head(n){}
    explicit HeavyLightDecomposition(vector<vector<int>> &G) : n(G.size()), G(G), par(n), dep(n), sub_size(n, 1), id(n), id_inv(n), tree_id(n), head(n) {}

    void add_edge(int u, int v){
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    void build(vector<int> roots = {0}){
        fill(par.begin(), par.end(), -1);
        fill(dep.begin(), dep.end(), 0);
        fill(sub_size.begin(), sub_size.end(), 1);
        int c = 0, pos = 0;
        for (auto &&i : roots) {
            dfs_sz(i);
            head[i] = i;
            dfs_hld(i, c++, pos);
        }
    }

    int lca(int u, int v){
        while(true){
            if(id[u] > id[v]) swap(u, v);
            if(head[u] == head[v]) return u;
            v = par[head[v]];
        }
    }

    int parent(int v) const {
        return par[v];
    }

    int ancestor(int v, int k) {
        if(dep[v] < k) return -1;
        while(true) {
            int u = head[v];
            if(id[v] - k >= id[u]) return id_inv[id[v] - k];
            k -= id[v]-id[u]+1;
            v = par[u];
        }
    }

    int distance(int u, int v){ return dep[u] + dep[v] - 2*dep[lca(u, v)]; }

    pair<int, int> subtree(int v, bool edge = false) const {
        return {id[v] + edge, id[v] + sub_size[v]};
    }

    template<typename F>
    void add(int u, int v, const F &f, bool edge){
        while (head[u] != head[v]){
            if(id[u] > id[v]) swap(u, v);
            f(id[head[v]], id[v]+1);
            v = par[head[v]];
        }
        if(id[u] > id[v]) swap(u, v);
        f(id[u]+edge, id[v]+1);
    }

    template<typename F>
    void path(int u, int v, const F &f, bool edge = false){
        add(u, v, f, edge);
    }

    template<typename F>
    void apply_subtree(int v, const F &f, bool edge = false){
        auto [l, r] = subtree(v, edge);
        f(l, r);
    }

    template<typename T, typename Q, typename F>
    T query(int u, int v, const T &e, const Q &q, const F &f, bool edge){
        T l = e, r = e;
        while(head[u] != head[v]){
            if(id[u] > id[v]) swap(u, v), swap(l, r);
            l = f(l, q(id[head[v]], id[v]+1));
            v = par[head[v]];
        }
        if(id[u] > id[v]) swap(u, v), swap(l, r);
        return f(q(id[u]+edge, id[v]+1), f(l, r));
    }

    template<typename T, typename Q, typename F>
    T path_query(int u, int v, const T &e, const Q &q, const F &f, bool edge = false){
        return query(u, v, e, q, f, edge);
    }

    template<typename T, typename QL, typename QR, typename F>
    T query_order(int u, int v, const T &e, const QL &ql, const QR &qr, const F &f, bool edge){
        T l = e, r = e;
        while(head[u] != head[v]){
            if(id[u] > id[v]) {
                l = f(l, qr(id[head[u]], id[u]+1));
                u = par[head[u]];
            }else {
                r = f(ql(id[head[v]], id[v]+1), r);
                v = par[head[v]];
            }
        }
        T mid = (id[u] > id[v] ? qr(id[v]+edge, id[u]+1) : ql(id[u]+edge, id[v]+1));
        return f(f(l, mid), r);
    }

    template<typename T, typename QL, typename QR, typename F>
    T path_query_ordered(int u, int v, const T &e, const QL &ql, const QR &qr, const F &f, bool edge = false){
        return query_order(u, v, e, ql, qr, f, edge);
    }

    template<typename T, typename Q>
    T subtree_query(int v, const Q &q, bool edge = false){
        auto [l, r] = subtree(v, edge);
        return q(l, r);
    }
};

/**
 * @brief HL分解(HL Decomposition)
 */
#line 2 "tree/hld_edge.cpp"

struct HeavyLightDecompositionEdge {
    HeavyLightDecomposition hld;

    explicit HeavyLightDecompositionEdge(int n) : hld(n) {}
    explicit HeavyLightDecompositionEdge(vector<vector<int>> &g) : hld(g) {}

    void add_edge(int u, int v) {
        hld.add_edge(u, v);
    }

    void build(vector<int> roots = {0}) {
        hld.build(roots);
    }

    int lca(int u, int v) {
        return hld.lca(u, v);
    }

    int parent(int v) const {
        return hld.parent(v);
    }

    int ancestor(int v, int k) {
        return hld.ancestor(v, k);
    }

    int distance(int u, int v) {
        return hld.distance(u, v);
    }

    int edge_index(int v) const {
        if (hld.par[v] == -1) return -1;
        return hld.id[v];
    }

    pair<int, int> subtree(int v) const {
        return hld.subtree(v, true);
    }

    template<typename F>
    void path(int u, int v, const F &f) {
        hld.path(u, v, f, true);
    }

    template<typename F>
    void apply_subtree(int v, const F &f) {
        hld.apply_subtree(v, f, true);
    }

    template<typename T, typename Q, typename F>
    T path_query(int u, int v, const T &e, const Q &q, const F &f) {
        return hld.path_query(u, v, e, q, f, true);
    }

    template<typename T, typename QL, typename QR, typename F>
    T path_query_ordered(int u, int v, const T &e, const QL &ql, const QR &qr, const F &f) {
        return hld.path_query_ordered(u, v, e, ql, qr, f, true);
    }

    template<typename T, typename Q>
    T subtree_query(int v, const Q &q) {
        return hld.subtree_query<T>(v, q, true);
    }
};

/**
 * @brief HL分解(辺クエリ)
 */

HL分解(辺クエリ) (tree/hld_edge.cpp)

説明