lib/tree/auxiliary_tree.hpp

• View this file on GitHub
• Last update: 2025-07-09 13:18:43+09:00
• Include: #include "lib/tree/auxiliary_tree.hpp"

Depends on

• 線形 Sparse Table (lib/data_structure/linear_sparse_table.hpp)
• スパーステーブル (lib/data_structure/sparse_table.hpp)
• 重み付きグラフ (lib/graph/graph.hpp)
• lib/internal/internal_csr.hpp
• オイラーツアー (lib/tree/euler_tour.hpp)
• lib/tree/linear_lca.hpp

Verified with

• test/yukicoder/0901.test.cpp

Code

#pragma once
#include <algorithm>
#include <stack>
#include <vector>
#include "graph/graph.hpp"
#include "tree/euler_tour.hpp"
#include "tree/linear_lca.hpp"

struct auxiliary_tree : public Graph<void> {
    auxiliary_tree(const std::vector<int> &_ord, const std::vector<int> &_par,
                   const std::vector<bool> &_f)
        : Graph::Graph(_par.size()), ord(_ord), f(_f) {
        int n = _par.size();
        for (int i = 0; i < n; ++i) {
            if (_par[i] != -1) add_edges(_par[i], i);
        }
    }

    int vertex(int x) const { return ord[x]; }
    bool contains(int x) const { return f[x]; }

  private:
    std::vector<int> ord;
    std::vector<bool> f;
};

struct auxiliary_tree_builder {
    template <class T>
    auxiliary_tree_builder(const Graph<T> &g, int r = 0) : lca(g, r), et(g, r) {}

    auxiliary_tree build(std::vector<int> v) {
        std::sort(v.begin(), v.end(), [&](int x, int y) { return et.order(x) < et.order(y); });
        v.erase(std::unique(v.begin(), v.end()), v.end());
        std::vector<int> ord = v;
        int k = ord.size();
        for (int i = 0; i < k - 1; ++i) ord.emplace_back(lca(ord[i], ord[i + 1]));
        std::sort(ord.begin(), ord.end(), [&](int x, int y) { return et.order(x) < et.order(y); });
        ord.erase(std::unique(ord.begin(), ord.end()), ord.end());

        int m = ord.size();
        std::vector<int> par(m);
        std::stack<int> st;
        for (int i = 0; i < m; ++i) {
            while (!st.empty() && et.right(ord[st.top()]) <= et.left(ord[i])) st.pop();
            par[i] = (st.empty() ? -1 : st.top());
            st.emplace(i);
        }
        std::vector<bool> f(m);
        int x = 0;
        for (int i = 0; i < m; ++i) {
            if (x < k && ord[i] == v[x]) {
                f[i] = true;
                ++x;
            }
        }
        return auxiliary_tree{ord, par, f};
    }

  private:
    linear_lca lca;
    euler_tour et;
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: graph/graph.hpp: line -1: no such header

Back to top page