icpc_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ebi-fly13/icpc_library

:heavy_check_mark: LCA based Auxiliary Tree
(tree/lca_based_auxiliary_tree.hpp)

説明

頂点集合を与えて、それらとそれらの頂点のLCAを合わせた補助的な木を求める。 返り値ではdfs順に{頂点番号, その親}が入っている。

頂点集合の大きさを $k$ として $O(k\log k)$

Depends on

Verified with

Code

#pragma once

#include "../tree/HeavyLightDecomposition.hpp"

namespace lib {

using namespace std;

vector<pair<int, int>> HeavyLightDecomposition::lca_based_auxiliary_tree(
    vector<int> vs) {
    if (vs.empty()) return {};
    sort(all(vs), [&](int u, int v) { return in[u] < in[v]; });
    auto s = vs;
    for (int i = 1; i < int(vs.size()); i++) {
        s.emplace_back(lca(vs[i - 1], vs[i]));
    }
    std::sort(all(s), [&](int u, int v) { return in[u] < in[v]; });
    s.erase(unique(all(s)), s.end());
    stack<int> st;
    st.push(s[0]);
    int sz = s.size();
    std::vector<std::pair<int, int>> dfs_order(sz);
    dfs_order[0] = {s[0], -1};
    rep(i, 1, sz) {
        int v = s[i];
        while (!st.empty()) {
            int u = st.top();
            if (in[u] <= in[v] && in[v] < out[u]) {
                break;
            } else {
                st.pop();
            }
        }
        assert(!st.empty());
        int par = st.top();
        dfs_order[i] = {v, par};
        st.push(v);
    }
    return dfs_order;
}

}  // namespace lib
#line 2 "tree/lca_based_auxiliary_tree.hpp"

#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
#line 4 "tree/lca_based_auxiliary_tree.hpp"

namespace lib {

using namespace std;

vector<pair<int, int>> HeavyLightDecomposition::lca_based_auxiliary_tree(
    vector<int> vs) {
    if (vs.empty()) return {};
    sort(all(vs), [&](int u, int v) { return in[u] < in[v]; });
    auto s = vs;
    for (int i = 1; i < int(vs.size()); i++) {
        s.emplace_back(lca(vs[i - 1], vs[i]));
    }
    std::sort(all(s), [&](int u, int v) { return in[u] < in[v]; });
    s.erase(unique(all(s)), s.end());
    stack<int> st;
    st.push(s[0]);
    int sz = s.size();
    std::vector<std::pair<int, int>> dfs_order(sz);
    dfs_order[0] = {s[0], -1};
    rep(i, 1, sz) {
        int v = s[i];
        while (!st.empty()) {
            int u = st.top();
            if (in[u] <= in[v] && in[v] < out[u]) {
                break;
            } else {
                st.pop();
            }
        }
        assert(!st.empty());
        int par = st.top();
        dfs_order[i] = {v, par};
        st.push(v);
    }
    return dfs_order;
}

}  // namespace lib
Back to top page