This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "tree/dp_on_static_top_tree.hpp"
$1$ 点更新・木DP計算が可能なデータ構造である。
必要な関数は以下である。
compress(Path p, Path c) -> Path
rake(Point a, Point b) -> Point
add_edge(Path a) -> Point
add_vertex(Point a, Path v) -> Path
AtCoder Beginner Contest 351 解説
#pragma once #include "../tree/static_top_tree.hpp" namespace ebi { template <class T, class Path, class Point, class Compress, class Rake, class Add_edge, class Add_vertex> struct dp_on_static_top_tree { private: void dfs(int v) { auto [lch, rch] = stt.child(v); if (lch != -1) dfs(lch); if (rch != -1) dfs(rch); update_(v); } void update_(int v) { if (stt.type(v) == Type::Vertex) { path[v] = vertex[v]; } else if (stt.type(v) == Type::Compress) { path[v] = compress(path[stt.left_child(v)], path[stt.right_child(v)]); } else if (stt.type(v) == Type::Rake) { point[v] = rake(point[stt.left_child(v)], point[stt.right_child(v)]); } else if (stt.type(v) == Type::AddEdge) { point[v] = add_edge(path[stt.left_child(v)]); } else if (stt.type(v) == Type::AddVertex) { path[v] = add_vertex(point[stt.left_child(v)], vertex[v]); } } void update(int v) { while (v != -1) { update_(v); v = stt.parent(v); } } public: dp_on_static_top_tree(const Graph<T> &g, int root, const std::vector<Path> &vertex_, const Compress &compress_, const Rake &rake_, const Add_edge &add_edge_, const Add_vertex &add_vertex_) : stt(g, root), n(stt.node_num()), path(n), point(n), vertex(vertex_), compress(compress_), rake(rake_), add_edge(add_edge_), add_vertex(add_vertex_) { dfs(stt.root()); } Path get() const { return path[stt.root()]; } void set(int v, Path x) { vertex[v] = x; update(v); } private: static_top_tree<T> stt; int n; std::vector<Path> path; std::vector<Point> point; std::vector<Path> vertex; const Compress compress; const Rake rake; const Add_edge add_edge; const Add_vertex add_vertex; }; } // namespace ebi
#line 2 "tree/dp_on_static_top_tree.hpp" #line 2 "tree/static_top_tree.hpp" #line 2 "graph/base.hpp" #include <cassert> #include <iostream> #include <ranges> #include <vector> #line 2 "data_structure/simple_csr.hpp" #line 4 "data_structure/simple_csr.hpp" #include <utility> #line 6 "data_structure/simple_csr.hpp" namespace ebi { template <class E> struct simple_csr { simple_csr() = default; simple_csr(int n, const std::vector<std::pair<int, E>>& elements) : start(n + 1, 0), elist(elements.size()) { for (auto e : elements) { start[e.first + 1]++; } for (auto i : std::views::iota(0, n)) { start[i + 1] += start[i]; } auto counter = start; for (auto [i, e] : elements) { elist[counter[i]++] = e; } } simple_csr(const std::vector<std::vector<E>>& es) : start(es.size() + 1, 0) { int n = es.size(); for (auto i : std::views::iota(0, n)) { start[i + 1] = (int)es[i].size() + start[i]; } elist.resize(start.back()); for (auto i : std::views::iota(0, n)) { std::copy(es[i].begin(), es[i].end(), elist.begin() + start[i]); } } int size() const { return (int)start.size() - 1; } const auto operator[](int i) const { return std::ranges::subrange(elist.begin() + start[i], elist.begin() + start[i + 1]); } auto operator[](int i) { return std::ranges::subrange(elist.begin() + start[i], elist.begin() + start[i + 1]); } const auto operator()(int i, int l, int r) const { return std::ranges::subrange(elist.begin() + start[i] + l, elist.begin() + start[i + 1] + r); } auto operator()(int i, int l, int r) { return std::ranges::subrange(elist.begin() + start[i] + l, elist.begin() + start[i + 1] + r); } private: std::vector<int> start; std::vector<E> elist; }; } // namespace ebi #line 9 "graph/base.hpp" namespace ebi { template <class T> struct Edge { int from, to; T cost; int id; }; template <class E> struct Graph { using cost_type = E; using edge_type = Edge<cost_type>; Graph(int n_) : n(n_) {} Graph() = default; void add_edge(int u, int v, cost_type c) { buff.emplace_back(u, edge_type{u, v, c, m}); edges.emplace_back(edge_type{u, v, c, m++}); } void add_undirected_edge(int u, int v, cost_type c) { buff.emplace_back(u, edge_type{u, v, c, m}); buff.emplace_back(v, edge_type{v, u, c, m}); edges.emplace_back(edge_type{u, v, c, m}); m++; } void read_tree(int offset = 1, bool is_weighted = false) { read_graph(n - 1, offset, false, is_weighted); } void read_parents(int offset = 1) { for (auto i : std::views::iota(1, n)) { int p; std::cin >> p; p -= offset; add_undirected_edge(p, i, 1); } build(); } void read_graph(int e, int offset = 1, bool is_directed = false, bool is_weighted = false) { for (int i = 0; i < e; i++) { int u, v; std::cin >> u >> v; u -= offset; v -= offset; if (is_weighted) { cost_type c; std::cin >> c; if (is_directed) { add_edge(u, v, c); } else { add_undirected_edge(u, v, c); } } else { if (is_directed) { add_edge(u, v, 1); } else { add_undirected_edge(u, v, 1); } } } build(); } void build() { assert(!prepared); csr = simple_csr<edge_type>(n, buff); buff.clear(); prepared = true; } int size() const { return n; } int node_number() const { return n; } int edge_number() const { return m; } edge_type get_edge(int i) const { return edges[i]; } std::vector<edge_type> get_edges() const { return edges; } const auto operator[](int i) const { return csr[i]; } auto operator[](int i) { return csr[i]; } private: int n, m = 0; std::vector<std::pair<int,edge_type>> buff; std::vector<edge_type> edges; simple_csr<edge_type> csr; bool prepared = false; }; } // namespace ebi #line 4 "tree/static_top_tree.hpp" namespace ebi { enum Type { Vertex, Compress, Rake, AddEdge, AddVertex }; template <class T> struct static_top_tree { private: struct Node { int par = -1, lch = -1, rch = -1; Type ty = Type::Vertex; }; void dfs_sz(int v) { for (auto &e : g[v]) { if (e.to == par[v]) continue; par[e.to] = v; dfs_sz(e.to); sz[v] += sz[e.to]; if (sz[e.to] > sz[g[v][0].to] || g[v][0].to == par[v]) { std::swap(e, g[v][0]); } } } int new_node(int k, int l, int r, Type t) { if (k == -1) { k = (int)stt.size(); stt.emplace_back(-1, l, r, t); } else { stt[k].lch = l; stt[k].rch = r; stt[k].ty = t; } if (l != -1) stt[l].par = k; if (r != -1) stt[r].par = k; return k; } std::pair<int, int> merge(const std::vector<std::pair<int, int>> &a, Type t) { if (a.size() == 1) { return a[0]; } int sum = 0; for (auto [v_, s] : a) sum += s; std::vector<std::pair<int, int>> b, c; for (auto [i, s] : a) { if (sum > s) b.emplace_back(i, s); else c.emplace_back(i, s); sum -= 2 * s; } auto [i, si] = merge(b, t); auto [j, sj] = merge(c, t); return {new_node(-1, i, j, t), si + sj}; } std::pair<int, int> compress(int v) { std::vector<std::pair<int, int>> path{add_vertex(v)}; while (g[v][0].to != par[v]) { path.emplace_back(add_vertex(v = g[v][0].to)); } return merge(path, Type::Compress); } std::pair<int, int> rake(int v) { std::vector<std::pair<int, int>> ch; for (int i = 1; i < (int)g[v].size(); i++) { if (g[v][i].to == par[v]) continue; ch.emplace_back(add_edge(g[v][i].to)); } return ch.empty() ? std::pair<int, int>{-1, 0} : merge(ch, Type::Rake); } std::pair<int, int> add_edge(int v) { auto [i, si] = compress(v); return {new_node(-1, i, -1, Type::AddEdge), si}; } std::pair<int, int> add_vertex(int v) { auto [i, si] = rake(v); return {new_node(v, i, -1, i == -1 ? Type::Vertex : Type::AddVertex), si + 1}; } public: static_top_tree(Graph<T> g_, int root = 0) : n(g_.size()), g(g_), par(n, -1), sz(n, 1), stt(n) { if (n == 1) { stt_root = 0; return; } dfs_sz(root); stt_root = compress(root).first; } int node_num() const { return (int)stt.size(); } int parent(int v) const { return stt[v].par; } std::pair<int, int> child(int v) const { return {stt[v].lch, stt[v].rch}; } int left_child(int v) const { return stt[v].lch; } int right_child(int v) const { return stt[v].rch; } Type type(int v) const { return stt[v].ty; } int root() const { return stt_root; } private: int n; Graph<T> g; std::vector<int> par, sz; std::vector<Node> stt; int stt_root; }; } // namespace ebi #line 4 "tree/dp_on_static_top_tree.hpp" namespace ebi { template <class T, class Path, class Point, class Compress, class Rake, class Add_edge, class Add_vertex> struct dp_on_static_top_tree { private: void dfs(int v) { auto [lch, rch] = stt.child(v); if (lch != -1) dfs(lch); if (rch != -1) dfs(rch); update_(v); } void update_(int v) { if (stt.type(v) == Type::Vertex) { path[v] = vertex[v]; } else if (stt.type(v) == Type::Compress) { path[v] = compress(path[stt.left_child(v)], path[stt.right_child(v)]); } else if (stt.type(v) == Type::Rake) { point[v] = rake(point[stt.left_child(v)], point[stt.right_child(v)]); } else if (stt.type(v) == Type::AddEdge) { point[v] = add_edge(path[stt.left_child(v)]); } else if (stt.type(v) == Type::AddVertex) { path[v] = add_vertex(point[stt.left_child(v)], vertex[v]); } } void update(int v) { while (v != -1) { update_(v); v = stt.parent(v); } } public: dp_on_static_top_tree(const Graph<T> &g, int root, const std::vector<Path> &vertex_, const Compress &compress_, const Rake &rake_, const Add_edge &add_edge_, const Add_vertex &add_vertex_) : stt(g, root), n(stt.node_num()), path(n), point(n), vertex(vertex_), compress(compress_), rake(rake_), add_edge(add_edge_), add_vertex(add_vertex_) { dfs(stt.root()); } Path get() const { return path[stt.root()]; } void set(int v, Path x) { vertex[v] = x; update(v); } private: static_top_tree<T> stt; int n; std::vector<Path> path; std::vector<Point> point; std::vector<Path> vertex; const Compress compress; const Rake rake; const Add_edge add_edge; const Add_vertex add_vertex; }; } // namespace ebi