Heavy Light Decomposition
(tree/HeavyLightDecomposition.hpp)

• View this file on GitHub
• Last update: 2023-11-24 15:39:05+09:00
• Include: #include "tree/HeavyLightDecomposition.hpp"

説明

木をHLDする。パスクエリ、部分木クエリを処理することができる。

コンストラクタ

HeavyLightDecomposition(std::vector<std::vector<int>> g, int root = 0)

木グラフ g と root ノード番号を与えてHLDする。デフォルトで root は頂点 0

idx(int u)

頂点 u のDFS行きがけ順の番号を返す。このidxの位置にデータ構造のインデックスを対応させればパスクエリや部分木クエリを処理することができる。具体的には使い方を参照。

lca(int u, int v)

頂点 u, v のLCAを返す。

distance(int u, int v)

頂点 u, v の距離を返す。

path_noncommutative_query(int u, int v, bool vertex, const F &f)

パス u-v にクエリfを適用する。非可換。vertexがtrueのとき、頂点に属性がある。vertexがfalseのとき、辺に属性がある。親-子間の辺属性は子のidxに持つ。

subtree_query(int u, bool vertex, const F &f)

頂点 u の部分木にクエリfを適用する。vertexがtrueのとき、根頂点である u にもクエリを適用する。

使い方

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> g(n);
    rep(i,0,m) {
        int u,v;
        std::cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    lib::HeavyLightDecomposition hld(g);
    segtree<S, op, e> seg1(n) 
    segtree<S, op_rev, e> seg2(n);
    auto set = [&](int u, S x) {
        int idx = hld.idx(u);
        seg1.set(idx, x);
        seg2.set(idx, x);
    };
    S ans = e();
    auto f = [&](int l, int r) {
        if(l <= r) ans = op(ans, seg1.prod(l, r));
        else ans = op(ans, seg2.prod(r, l)); 
    };
    int u,v;
    std::cin >> u >> v;
    ans = e();
    hld.path_noncommutative_query(u, v, true, f);
    std::cout << ans << '\n';
}

Depends on

• テンプレート (template/template.hpp)

Required by

• LCA based Auxiliary Tree (tree/lca_based_auxiliary_tree.hpp)

Verified with

• test/data_structure/Vertex_Add_Path_Sum.test.cpp
• test/tree/yuki_901.test.cpp

Code

#pragma once

#include "../template/template.hpp"

namespace lib {

using namespace std;

struct HeavyLightDecomposition {
  private:
    void dfs_sz(int v) {
        for (auto &nv : g[v]) {
            if (nv == par[v]) continue;
            par[nv] = v;
            depth[nv] = depth[v] + 1;
            dfs_sz(nv);
            sz[v] += sz[nv];
            if (sz[nv] > sz[g[v][0]] || g[v][0] == par[v]) swap(nv, g[v][0]);
        }
    }

    void dfs_hld(int v) {
        in[v] = t++;
        for (auto nv : g[v]) {
            if (nv == par[v]) continue;
            nxt[nv] = (nv == g[v][0] ? nxt[v] : nv);
            dfs_hld(nv);
        }
        out[v] = t;
    }

    // [u, v) パスの取得 (v は u の祖先)
    vector<pair<int, int>> ascend(int u, int v) const {
        vector<pair<int, int>> res;
        while (nxt[u] != nxt[v]) {
            res.emplace_back(in[u], in[nxt[u]]);
            u = par[nxt[u]];
        }
        if (u != v) res.emplace_back(in[u], in[v] + 1);
        return res;
    }

    // (u, v] パスの取得 (u は v の祖先)
    vector<pair<int, int>> descend(int u, int v) const {
        if (u == v) return {};
        if (nxt[u] == nxt[v]) return {{in[u] + 1, in[v]}};
        auto res = descend(u, par[nxt[v]]);
        res.emplace_back(in[nxt[v]], in[v]);
        return res;
    }

  public:
    HeavyLightDecomposition(const vector<vector<int>> &gh, int root = 0)
        : n(gh.size()),
          g(gh),
          sz(n, 1),
          in(n),
          out(n),
          nxt(n),
          par(n, -1),
          depth(n, 0) {
        nxt[root] = root;
        dfs_sz(root);
        dfs_hld(root);
    }

    int idx(int u) const {
        return in[u];
    }

    int lca(int u, int v) const {
        while (nxt[u] != nxt[v]) {
            if (in[u] < in[v]) swap(u, v);
            u = par[nxt[u]];
        }
        return depth[u] < depth[v] ? u : v;
    }

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

    template <class F>
    void path_noncommutative_query(int u, int v, bool vertex,
                                   const F &f) const {
        int l = lca(u, v);
        for (auto [a, b] : ascend(u, l)) f(a + 1, b);
        if (vertex) f(in[l], in[l] + 1);
        for (auto [a, b] : descend(l, v)) f(a, b + 1);
    }

    template <class F> void subtree_query(int u, bool vertex, const F &f) {
        f(in[u] + int(!vertex), out[u]);
    }

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

    std::vector<std::pair<int,int>> lca_based_auxiliary_tree(std::vector<int>);

  private:
    int n, t = 0;
    vector<vector<int>> g;
    vector<int> sz, in, out, nxt, par, depth;
};

}  // namespace lib

#line 2 "tree/HeavyLightDecomposition.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "tree/HeavyLightDecomposition.hpp"

namespace lib {

using namespace std;

struct HeavyLightDecomposition {
  private:
    void dfs_sz(int v) {
        for (auto &nv : g[v]) {
            if (nv == par[v]) continue;
            par[nv] = v;
            depth[nv] = depth[v] + 1;
            dfs_sz(nv);
            sz[v] += sz[nv];
            if (sz[nv] > sz[g[v][0]] || g[v][0] == par[v]) swap(nv, g[v][0]);
        }
    }

    void dfs_hld(int v) {
        in[v] = t++;
        for (auto nv : g[v]) {
            if (nv == par[v]) continue;
            nxt[nv] = (nv == g[v][0] ? nxt[v] : nv);
            dfs_hld(nv);
        }
        out[v] = t;
    }

    // [u, v) パスの取得 (v は u の祖先)
    vector<pair<int, int>> ascend(int u, int v) const {
        vector<pair<int, int>> res;
        while (nxt[u] != nxt[v]) {
            res.emplace_back(in[u], in[nxt[u]]);
            u = par[nxt[u]];
        }
        if (u != v) res.emplace_back(in[u], in[v] + 1);
        return res;
    }

    // (u, v] パスの取得 (u は v の祖先)
    vector<pair<int, int>> descend(int u, int v) const {
        if (u == v) return {};
        if (nxt[u] == nxt[v]) return {{in[u] + 1, in[v]}};
        auto res = descend(u, par[nxt[v]]);
        res.emplace_back(in[nxt[v]], in[v]);
        return res;
    }

  public:
    HeavyLightDecomposition(const vector<vector<int>> &gh, int root = 0)
        : n(gh.size()),
          g(gh),
          sz(n, 1),
          in(n),
          out(n),
          nxt(n),
          par(n, -1),
          depth(n, 0) {
        nxt[root] = root;
        dfs_sz(root);
        dfs_hld(root);
    }

    int idx(int u) const {
        return in[u];
    }

    int lca(int u, int v) const {
        while (nxt[u] != nxt[v]) {
            if (in[u] < in[v]) swap(u, v);
            u = par[nxt[u]];
        }
        return depth[u] < depth[v] ? u : v;
    }

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

    template <class F>
    void path_noncommutative_query(int u, int v, bool vertex,
                                   const F &f) const {
        int l = lca(u, v);
        for (auto [a, b] : ascend(u, l)) f(a + 1, b);
        if (vertex) f(in[l], in[l] + 1);
        for (auto [a, b] : descend(l, v)) f(a, b + 1);
    }

    template <class F> void subtree_query(int u, bool vertex, const F &f) {
        f(in[u] + int(!vertex), out[u]);
    }

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

    std::vector<std::pair<int,int>> lca_based_auxiliary_tree(std::vector<int>);

  private:
    int n, t = 0;
    vector<vector<int>> g;
    vector<int> sz, in, out, nxt, par, depth;
};

}  // namespace lib

Back to top page