C++ Library for Competitive Programming
#include "emthrm/graph/tree/euler_tour_technique.hpp"
根付き木を列として表現するデータ構造である。
$O(\lvert V \rvert)$
template <typename CostType>
struct EulerTourTechnique;
CostType
:辺のコストを表す型名前 | 説明 |
---|---|
std::vector<int> preorder |
頂点属性の Euler tour |
std::vector<int> depth |
depth[i] は頂点 preorder[i] の深さを表す。 |
std::vector<int> left |
left[i] は preorder に頂点 $i$ が現れるインデックスの最小値を表す。 |
std::vector<int> right |
right[i] は preorder に頂点 $i$ が現れるインデックスの最大値を表す。 |
std::vector<int> down |
down[i] は tour に頂点 $i$ へ下る辺が現れるインデックスを表す。 |
std::vector<int> up |
up[i] は tour に頂点 $i$ から上る辺が現れるインデックスを表す。 |
std::vector<CostType> tour |
Euler tour |
名前 | 効果・戻り値 |
---|---|
explicit EulerTourTechnique(const std::vector<std::vector<Edge<CostType>>> &graph, const int root = 0); |
根を $\mathrm{root}$ とする木 $\mathrm{graph}$ に対してオブジェクトを構築する。 |
template <typename Fn> void update_v(const int ver, const Fn f) const;
|
頂点 $\mathrm{ver}$ の部分木の頂点に対して $f$ を基に更新する。 |
template <typename T, typename Fn> T query_v(const int ver, const Fn f) const;
|
頂点 $\mathrm{ver}$ の部分木の頂点に対する $f$ を基にしたクエリの解 |
template <typename T, typename Fn> T query_e(const int u, const int v, const Fn f) const;
|
頂点 $u$ から $v$ へ下る辺に対する $f$ を基にしたクエリの解 |
template <typename Fn> void update_subtree_e(const int ver, const Fn f) const;
|
頂点 $\mathrm{ver}$ の部分木の辺に対して $f$ を基に更新する。 |
template <typename T, typename Fn> T query_subtree_e(const int ver, const Fn f) const;
|
頂点 $\mathrm{ver}$ の部分木の辺に対する $f$ を基にしたクエリの解 |
https://onlinejudge.u-aizu.ac.jp/solutions/problem/2667/review/4084875/emthrm/C++14
#ifndef EMTHRM_GRAPH_TREE_EULER_TOUR_TECHNIQUE_HPP_
#define EMTHRM_GRAPH_TREE_EULER_TOUR_TECHNIQUE_HPP_
#include <vector>
#include "emthrm/graph/edge.hpp"
namespace emthrm {
template <typename CostType>
struct EulerTourTechnique {
std::vector<int> preorder, depth, left, right, down, up;
std::vector<CostType> tour;
explicit EulerTourTechnique(
const std::vector<std::vector<Edge<CostType>>> &graph, const int root = 0)
: graph(graph) {
const int n = graph.size();
left.resize(n);
right.resize(n);
down.assign(n, -1);
up.assign(n, (n - 1) << 1);
dfs(-1, root, 0);
}
template <typename Fn>
void update_v(const int ver, const Fn f) const {
f(left[ver], right[ver] + 1);
}
template <typename T, typename Fn>
T query_v(const int ver, const Fn f) const {
return f(left[ver], right[ver] + 1);
}
template <typename T, typename Fn>
T query_e(const int u, const int v, const Fn f) const {
return f(down[u] + 1, down[v] + 1);
}
template <typename Fn>
void update_subtree_e(const int ver, const Fn f) const {
f(down[ver] + 1, up[ver]);
}
template <typename T, typename Fn>
T query_subtree_e(const int ver, const Fn f) const {
return f(down[ver] + 1, up[ver]);
}
private:
const std::vector<std::vector<Edge<CostType>>> graph;
void dfs(const int par, const int ver, const int cur_depth) {
left[ver] = preorder.size();
preorder.emplace_back(ver);
depth.emplace_back(cur_depth);
for (const Edge<CostType>& e : graph[ver]) {
if (e.dst != par) {
down[e.dst] = tour.size();
tour.emplace_back(e.cost);
dfs(ver, e.dst, cur_depth + 1);
preorder.emplace_back(ver);
depth.emplace_back(cur_depth);
up[e.dst] = tour.size();
tour.emplace_back(-e.cost);
}
}
right[ver] = preorder.size() - 1;
}
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_TREE_EULER_TOUR_TECHNIQUE_HPP_
#line 1 "include/emthrm/graph/tree/euler_tour_technique.hpp"
#include <vector>
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template <typename CostType>
struct Edge {
CostType cost;
int src, dst;
explicit Edge(const int src, const int dst, const CostType cost = 0)
: cost(cost), src(src), dst(dst) {}
auto operator<=>(const Edge& x) const = default;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 7 "include/emthrm/graph/tree/euler_tour_technique.hpp"
namespace emthrm {
template <typename CostType>
struct EulerTourTechnique {
std::vector<int> preorder, depth, left, right, down, up;
std::vector<CostType> tour;
explicit EulerTourTechnique(
const std::vector<std::vector<Edge<CostType>>> &graph, const int root = 0)
: graph(graph) {
const int n = graph.size();
left.resize(n);
right.resize(n);
down.assign(n, -1);
up.assign(n, (n - 1) << 1);
dfs(-1, root, 0);
}
template <typename Fn>
void update_v(const int ver, const Fn f) const {
f(left[ver], right[ver] + 1);
}
template <typename T, typename Fn>
T query_v(const int ver, const Fn f) const {
return f(left[ver], right[ver] + 1);
}
template <typename T, typename Fn>
T query_e(const int u, const int v, const Fn f) const {
return f(down[u] + 1, down[v] + 1);
}
template <typename Fn>
void update_subtree_e(const int ver, const Fn f) const {
f(down[ver] + 1, up[ver]);
}
template <typename T, typename Fn>
T query_subtree_e(const int ver, const Fn f) const {
return f(down[ver] + 1, up[ver]);
}
private:
const std::vector<std::vector<Edge<CostType>>> graph;
void dfs(const int par, const int ver, const int cur_depth) {
left[ver] = preorder.size();
preorder.emplace_back(ver);
depth.emplace_back(cur_depth);
for (const Edge<CostType>& e : graph[ver]) {
if (e.dst != par) {
down[e.dst] = tour.size();
tour.emplace_back(e.cost);
dfs(ver, e.dst, cur_depth + 1);
preorder.emplace_back(ver);
depth.emplace_back(cur_depth);
up[e.dst] = tour.size();
tour.emplace_back(-e.cost);
}
}
right[ver] = preorder.size() - 1;
}
};
} // namespace emthrm