cp-library
C++ Library for Competitive Programming
グラフ/木/heavy-light decomposition（最小共通祖先）
(test/graph/tree/heavy-light_decomposition.2.test.cpp)
- View this file on GitHub
- Last update: 2023-05-12 15:57:02+09:00
- Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C
Depends on
辺
(include/emthrm/graph/edge.hpp)
- heavy-light decomposition
(include/emthrm/graph/tree/heavy-light_decomposition.hpp)
Code
/*
* @title グラフ/木/heavy-light decomposition（最小共通祖先）
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C
*/
#include <iostream>
#include <vector>
#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/tree/heavy-light_decomposition.hpp"
int main() {
int n;
std::cin >> n;
std::vector<std::vector<emthrm::Edge<int>>> graph(n);
for (int i = 0; i < n; ++i) {
int k;
std::cin >> k;
while (k--) {
int c;
std::cin >> c;
graph[i].emplace_back(i, c, 1);
graph[c].emplace_back(c, i, 1);
}
}
const emthrm::HeavyLightDecomposition<int>
heavy_light_decomposition(graph, 0);
int q;
std::cin >> q;
while (q--) {
int u, v;
std::cin >> u >> v;
std::cout << heavy_light_decomposition.lowest_common_ancestor(u, v) << '\n';
}
return 0;
}#line 1 "test/graph/tree/heavy-light_decomposition.2.test.cpp"
/*
* @title グラフ/木/heavy-light decomposition（最小共通祖先）
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C
*/
#include <iostream>
#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 1 "include/emthrm/graph/tree/heavy-light_decomposition.hpp"
#include <algorithm>
#include <utility>
#line 7 "include/emthrm/graph/tree/heavy-light_decomposition.hpp"
#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 9 "include/emthrm/graph/tree/heavy-light_decomposition.hpp"
namespace emthrm {
template <typename CostType>
struct HeavyLightDecomposition {
std::vector<int> parent, subtree, id, inv, head;
std::vector<CostType> cost;
explicit HeavyLightDecomposition(
const std::vector<std::vector<Edge<CostType>>>& graph,
const int root = 0)
: graph(graph) {
const int n = graph.size();
parent.assign(n, -1);
subtree.assign(n, 1);
dfs1(root);
id.resize(n);
inv.resize(n);
head.assign(n, root);
int cur_id = 0;
dfs2(root, &cur_id);
}
template <typename Fn>
void update_v(int u, int v, const Fn f) const {
while (true) {
if (id[u] > id[v]) std::swap(u, v);
f(std::max(id[head[v]], id[u]), id[v] + 1);
if (head[u] == head[v]) break;
v = parent[head[v]];
}
}
template <typename F, typename G, typename T>
T query_v(int u, int v, const F f, const G g, const T id_t) const {
T left = id_t, right = id_t;
while (true) {
if (id_t[u] > id_t[v]) {
std::swap(u, v);
std::swap(left, right);
}
left = g(left, f(std::max(id_t[head[v]], id_t[u]), id_t[v] + 1));
if (head[u] == head[v]) break;
v = parent[head[v]];
}
return g(left, right);
}
template <typename Fn>
void update_subtree_v(const int ver, const Fn f) const {
f(id[ver], id[ver] + subtree[ver]);
}
template <typename T, typename Fn>
T query_subtree_v(const int ver, const Fn f) const {
return f(id[ver], id[ver] + subtree[ver]);
}
template <typename Fn>
void update_e(int u, int v, const Fn f) const {
while (true) {
if (id[u] > id[v]) std::swap(u, v);
if (head[u] == head[v]) {
f(id[u], id[v]);
break;
} else {
f(id[head[v]] - 1, id[v]);
v = parent[head[v]];
}
}
}
template <typename F, typename G, typename T>
T query_e(int u, int v, const F f, const G g, const T id_t) const {
T left = id_t, right = id_t;
while (true) {
if (id[u] > id[v]) {
std::swap(u, v);
std::swap(left, right);
}
if (head[u] == head[v]) {
left = g(left, f(id[u], id[v]));
break;
} else {
left = g(left, f(id[head[v]] - 1, id[v]));
v = parent[head[v]];
}
}
return g(left, right);
}
template <typename Fn>
void update_subtree_e(const int ver, const Fn f) const {
f(id[ver], id[ver] + subtree[ver] - 1);
}
template <typename T, typename Fn>
T query_subtree_e(const int ver, const Fn f) const {
return f(id[ver], id[ver] + subtree[ver] - 1);
}
int lowest_common_ancestor(int u, int v) const {
while (true) {
if (id[u] > id[v]) std::swap(u, v);
if (head[u] == head[v]) break;
v = parent[head[v]];
}
return u;
}
private:
std::vector<std::vector<Edge<CostType>>> graph;
void dfs1(const int ver) {
for (int i = 0; std::cmp_less(i, graph[ver].size()); ++i) {
Edge<CostType>& e = graph[ver][i];
if (e.dst != parent[ver]) {
parent[e.dst] = ver;
dfs1(e.dst);
subtree[ver] += subtree[e.dst];
if (subtree[e.dst] > subtree[graph[ver].front().dst]) {
std::swap(e, graph[ver].front());
}
}
}
}
void dfs2(const int ver, int* cur_id) {
id[ver] = (*cur_id)++;
inv[id[ver]] = ver;
for (const Edge<CostType>& e : graph[ver]) {
if (e.dst != parent[ver]) {
head[e.dst] = (e.dst == graph[ver].front().dst ? head[ver] : e.dst);
cost.emplace_back(e.cost);
dfs2(e.dst, cur_id);
}
}
}
};
} // namespace emthrm
#line 12 "test/graph/tree/heavy-light_decomposition.2.test.cpp"
int main() {
int n;
std::cin >> n;
std::vector<std::vector<emthrm::Edge<int>>> graph(n);
for (int i = 0; i < n; ++i) {
int k;
std::cin >> k;
while (k--) {
int c;
std::cin >> c;
graph[i].emplace_back(i, c, 1);
graph[c].emplace_back(c, i, 1);
}
}
const emthrm::HeavyLightDecomposition<int>
heavy_light_decomposition(graph, 0);
int q;
std::cin >> q;
while (q--) {
int u, v;
std::cin >> u >> v;
std::cout << heavy_light_decomposition.lowest_common_ancestor(u, v) << '\n';
}
return 0;
}