#line 2 "library/tree/AuxiliaryTree.hpp"
#line 2 "library/tree/HLD.hpp"
template <typename TREE> struct HLD {
int n;
TREE T;
std::vector<int> sz, head, id, id2, rev_id;
bool prepared;
HLD(TREE T_)
: T(T_), n(T_.n), sz(n), head(n), id(n), id2(n), rev_id(n), prepared(false) {}
HLD() = default;
private:
void dfs_sz(int v) {
sz[v] = 1;
for (auto &e : T.son(v)) {
dfs_sz(e.to);
sz[v] += sz[e.to];
if (sz[e.to] > sz[T.son(v)[0].to])
std::swap(e, T.son(v)[0]);
}
}
void dfs_hld(int v, int &k) {
id[v] = k++;
rev_id[id[v]] = v;
for (int i = 0; i < T.son(v).size(); i++) {
int to = T.son(v)[i];
head[to] = (i ? to : head[v]);
dfs_hld(to, k);
}
id2[v] = k;
}
public:
std::vector<int> build(int r = 0) {
assert(!prepared);
prepared = true;
if (~T.root)
assert(T.root == r);
else
T.build(r);
head[r] = r;
dfs_sz(r);
int k = 0;
dfs_hld(r, k);
return id;
}
int lca(int u, int v) const {
assert(prepared);
while (head[u] != head[v])
if (T.depth[head[u]] > T.depth[head[v]])
u = T.parent(head[u]);
else
v = T.parent(head[v]);
return (T.depth[u] < T.depth[v] ? u : v);
}
int distance(int u, int v) const {
int w = lca(u, v);
return T.depth[u] + T.depth[v] - T.depth[w] * 2;
}
// v の k 個上の頂点を返す
int kth_parent(int v, int k) const {
assert(prepared);
if(T.depth[v] < k)
return -1;
while(T.depth[v] - T.depth[head[v]] < k){
k -= T.depth[v] - T.depth[head[v]] + 1;
v = T.parent(head[v]);
}
return rev_id[id[v] - k];
}
// u から v へ k 回移動した頂点を返す
int jump(int u, int v, int k) const {
assert(prepared);
int w = lca(u, v);
if(T.depth[u] + T.depth[v] - T.depth[w] * 2 < k)
return -1;
if(T.depth[u] - T.depth[w] >= k)
return kth_parent(u, k);
return kth_parent(v, T.depth[u] + T.depth[v] - T.depth[w] * 2 - k);
}
// l=lca(u,v) とした時、[u,l] パスと [v,l] パス を閉区間の組みで返す
using path_t = std::vector<std::pair<int, int>>;
std::pair<path_t, path_t> path(int u, int v) const {
assert(prepared);
path_t path_u, path_v;
while (u != v) {
if (head[u] == head[v]) {
if (T.depth[u] < T.depth[v])
path_v.emplace_back(id[v], id[u]);
else
path_u.emplace_back(id[u], id[v]);
break;
}
if (T.depth[head[u]] < T.depth[head[v]]) {
path_v.emplace_back(id[v], id[head[v]]);
v = T.parent(head[v]);
} else {
path_u.emplace_back(id[u], id[head[u]]);
u = T.parent(head[u]);
}
}
if (u == v)
path_u.emplace_back(id[u], id[u]);
return {path_u, path_v};
}
// [l,r) が v の部分木
std::pair<int, int> subtree(int v) const {
assert(prepared);
return {id[v], id2[v]};
}
};
#line 2 "library/graph/Graph.hpp"
#include <cassert>
#include <iostream>
#include <vector>
struct Edge {
int from, to;
Edge() = default;
Edge(int from, int to) : from(from), to(to) {}
operator int() const { return to; }
};
struct Graph {
int n;
using edge_type = Edge;
std::vector<edge_type> edges;
protected:
std::vector<int> in_deg;
bool prepared;
class OutgoingEdges {
Graph *g;
int l, r;
public:
OutgoingEdges(Graph *g, int l, int r) : g(g), l(l), r(r) {}
edge_type *begin() { return &(g->edges[l]); }
edge_type *end() { return &(g->edges[r]); }
edge_type &operator[](int i) { return g->edges[l + i]; }
int size() const { return r - l; }
};
class ConstOutgoingEdges {
const Graph *g;
int l, r;
public:
ConstOutgoingEdges(const Graph *g, int l, int r) : g(g), l(l), r(r) {}
const edge_type *begin() const { return &(g->edges[l]); }
const edge_type *end() const { return &(g->edges[r]); }
const edge_type &operator[](int i) const { return g->edges[l + i]; }
int size() const { return r - l; }
};
public:
OutgoingEdges operator[](int v) {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
const ConstOutgoingEdges operator[](int v) const {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
bool is_prepared() const { return prepared; }
Graph() : n(0), in_deg(1, 0), prepared(false) {}
Graph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
Graph(int n, int m, bool directed = false, int indexed = 1)
: n(n), in_deg(n + 1, 0), prepared(false) {
scan(m, directed, indexed);
}
void resize(int n) { n = n; }
void add_arc(int from, int to) {
assert(!prepared);
assert(0 <= from and from < n and 0 <= to and to < n);
edges.emplace_back(from, to);
in_deg[from + 1]++;
}
void add_edge(int u, int v) {
add_arc(u, v);
add_arc(v, u);
}
void add_arc(const edge_type &e) { add_arc(e.from, e.to); }
void add_edge(const edge_type &e) { add_edge(e.from, e.to); }
void scan(int m, bool directed = false, int indexed = 1) {
edges.reserve(directed ? m : 2 * m);
while (m--) {
int u, v;
std::cin >> u >> v;
u -= indexed;
v -= indexed;
if (directed)
add_arc(u, v);
else
add_edge(u, v);
}
build();
}
void build() {
assert(!prepared);
prepared = true;
for (int v = 0; v < n; v++)
in_deg[v + 1] += in_deg[v];
std::vector<edge_type> new_edges(in_deg.back());
auto counter = in_deg;
for (auto &&e : edges)
new_edges[counter[e.from]++] = e;
edges = new_edges;
}
void graph_debug() const {
#ifndef __LOCAL
return;
#endif
assert(prepared);
for (int from = 0; from < n; from++) {
std::cerr << from << ";";
for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
std::cerr << edges[i].to << " ";
std::cerr << "\n";
}
}
};
#line 3 "library/tree/Tree.hpp"
struct Tree : Graph {
using Graph::Graph;
Tree() = default;
int root = -1;
std::vector<int> DFS, BFS, depth;
void scan_root(int indexed = 1) {
for (int i = 1; i < n; i++) {
int p;
std::cin >> p;
add_edge(p - indexed, i);
}
build();
}
void scan(int indexed = 1) {
Graph::scan(n - 1, false, indexed);
build();
}
edge_type &parent(int v) {
assert(~root and root != v);
return (*this)[v][0];
}
const edge_type &parent(int v) const {
assert(~root and root != v);
return (*this)[v][0];
}
OutgoingEdges son(int v) {
assert(~root);
if (v == root)
return {this, in_deg[v], in_deg[v + 1]};
return {this, in_deg[v] + 1, in_deg[v + 1]};
}
private:
void dfs(int v, int pre = -1) {
for (auto &e : (*this)[v]) {
if (e.to == pre)
std::swap((*this)[v][0], e);
else {
depth[e.to] = depth[v] + 1;
dfs(e.to, v);
}
}
DFS.push_back(v);
}
public:
void build(int r = 0) {
if (!is_prepared())
Graph::build();
if (~root) {
assert(r == root);
return;
}
root = r;
depth = std::vector<int>(n, 0);
DFS.reserve(n);
BFS.reserve(n);
dfs(root);
std::queue<int> que;
que.push(root);
while (que.size()) {
int p = que.front();
que.pop();
BFS.push_back(p);
for (const auto &e : son(p))
que.push(e.to);
}
}
};
#line 2 "library/graph/WeightedGraph.hpp"
template <typename T> struct WeightedEdge {
WeightedEdge() = default;
WeightedEdge(int from, int to, T weight)
: from(from), to(to), weight(weight) {}
int from, to;
T weight;
operator int() const { return to; }
};
template <typename T> struct WeightedGraph {
int n;
using weight_type = T;
using edge_type = WeightedEdge<T>;
std::vector<edge_type> edges;
protected:
std::vector<int> in_deg;
bool prepared;
class OutgoingEdges {
WeightedGraph *g;
int l, r;
public:
OutgoingEdges(WeightedGraph *g, int l, int r) : g(g), l(l), r(r) {}
edge_type *begin() { return &(g->edges[l]); }
edge_type *end() { return &(g->edges[r]); }
edge_type &operator[](int i) { return g->edges[l + i]; }
int size() const { return r - l; }
};
class ConstOutgoingEdges {
const WeightedGraph *g;
int l, r;
public:
ConstOutgoingEdges(const WeightedGraph *g, int l, int r)
: g(g), l(l), r(r) {}
const edge_type *begin() const { return &(g->edges[l]); }
const edge_type *end() const { return &(g->edges[r]); }
const edge_type &operator[](int i) const { return g->edges[l + i]; }
int size() const { return r - l; }
};
public:
OutgoingEdges operator[](int v) {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
const ConstOutgoingEdges operator[](int v) const {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
bool is_prepared() const { return prepared; }
WeightedGraph() : n(0), in_deg(1, 0), prepared(false) {}
WeightedGraph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
WeightedGraph(int n, int m, bool directed = false, int indexed = 1)
: n(n), in_deg(n + 1, 0), prepared(false) {
scan(m, directed, indexed);
}
void resize(int n) { n = n; }
void add_arc(int from, int to, T weight) {
assert(!prepared);
assert(0 <= from and from < n and 0 <= to and to < n);
edges.emplace_back(from, to, weight);
in_deg[from + 1]++;
}
void add_edge(int u, int v, T weight) {
add_arc(u, v, weight);
add_arc(v, u, weight);
}
void add_arc(const edge_type &e) { add_arc(e.from, e.to, e.weight); }
void add_edge(const edge_type &e) { add_edge(e.from, e.to, e.weight); }
void scan(int m, bool directed = false, int indexed = 1) {
edges.reserve(directed ? m : 2 * m);
while (m--) {
int u, v;
std::cin >> u >> v;
u -= indexed;
v -= indexed;
T weight;
std::cin >> weight;
if (directed)
add_arc(u, v, weight);
else
add_edge(u, v, weight);
}
build();
}
void build() {
assert(!prepared);
prepared = true;
for (int v = 0; v < n; v++)
in_deg[v + 1] += in_deg[v];
std::vector<edge_type> new_edges(in_deg.back());
auto counter = in_deg;
for (auto &&e : edges)
new_edges[counter[e.from]++] = e;
edges = new_edges;
}
void graph_debug() const {
#ifndef __DEBUG
return;
#endif
assert(prepared);
for (int from = 0; from < n; from++) {
std::cerr << from << ";";
for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
std::cerr << "(" << edges[i].to << "," << edges[i].weight
<< ")";
std::cerr << "\n";
}
}
};
#line 3 "library/tree/WeightedTree.hpp"
template <typename T> struct WeightedTree : WeightedGraph<T> {
using WeightedGraph<T>::WeightedGraph;
using edge_type = typename WeightedGraph<T>::edge_type;
using OutgoingEdges = typename WeightedGraph<T>::OutgoingEdges;
using WeightedGraph<T>::n;
using WeightedGraph<T>::in_deg;
int root = -1;
std::vector<int> DFS, BFS, depth;
void scan_root(int indexed = 1) {
for (int i = 1; i < n; i++) {
int p;
std::cin >> p;
T weight;
std::cin >> weight;
add_edge(p - indexed, i, weight);
}
build();
}
void scan(int indexed = 1) {
WeightedGraph<T>::scan(n - 1, false, indexed);
build();
}
edge_type &parent(int v) {
assert(~root and root != v);
return (*this)[v][0];
}
OutgoingEdges son(int v) {
assert(~root);
if (v == root)
return {this, in_deg[v], in_deg[v + 1]};
return {this, in_deg[v] + 1, in_deg[v + 1]};
}
private:
void dfs(int v, int pre = -1) {
for (auto &e : (*this)[v]) {
if (e.to == pre)
std::swap((*this)[v][0], e);
else {
depth[e.to] = depth[v] + 1;
dfs(e.to, v);
}
}
DFS.push_back(v);
}
public:
void build(int r = 0) {
if (!WeightedGraph<T>::is_prepared())
WeightedGraph<T>::build();
if (~root) {
assert(r == root);
return;
}
root = r;
depth = std::vector<int>(n, 0);
DFS.reserve(n);
BFS.reserve(n);
dfs(root);
std::queue<int> que;
que.push(root);
while (que.size()) {
int p = que.front();
que.pop();
BFS.push_back(p);
for (const auto &e : son(p))
que.push(e.to);
}
}
};
#line 2 "library/util/Compress.hpp"
template <typename T, bool Sentinel = false> class Compress {
std::vector<T> v;
bool prepared;
public:
Compress() : prepared(false) {
if constexpr (Sentinel) {
static_assert(std::numeric_limits<T>::is_specialized,
"cannot use Sentinel");
v = {std::numeric_limits<T>::min(), std::numeric_limits<T>::max()};
}
}
Compress(const std::vector<T> &w) : v(w), prepared(false) {
if constexpr (Sentinel) {
static_assert(std::numeric_limits<T>::is_specialized,
"cannot use Sentinel");
v.push_back(std::numeric_limits<T>::min());
v.push_back(std::numeric_limits<T>::max());
}
build();
}
void add(T a) {
assert(!prepared);
v.push_back(a);
}
void build() {
assert(!prepared);
prepared = true;
std::ranges::sort(v);
auto result = std::ranges::unique(v);
v.erase(result.begin(), result.end());
}
bool is_prepared() const { return prepared; }
int operator[](const T &a) const {
assert(prepared);
auto it = std::ranges::lower_bound(v, a);
assert(*it == a);
return std::distance(v.begin(), it);
}
int geq(const T &a) const {
assert(prepared);
auto it = std::ranges::lower_bound(v, a);
return std::distance(v.begin(), it);
}
int gt(const T &a) const {
assert(prepared);
auto it = std::ranges::upper_bound(v, a);
return std::distance(v.begin(), it);
}
int leq(const T &a) const {
assert(prepared);
auto it = --std::ranges::upper_bound(v, a);
return std::distance(v.begin(), it);
}
int lt(const T &a) const {
assert(prepared);
auto it = --std::ranges::lower_bound(v, a);
return std::distance(v.begin(), it);
}
T r(int id) const {
assert(prepared);
return v[id];
}
bool exist(const T &a) const {
assert(prepared);
return (*std::ranges::lower_bound(v, a)) == a;
}
int size() const { return v.size(); }
T max() const { return v.back(); }
T min() const { return v[0]; }
friend std::ostream &operator<<(std::ostream &os, const Compress &C) {
for (int i = 0; i < C.v.size(); i++)
os << C.v[i] << ":" << i << " ";
return os;
}
};
#line 7 "library/tree/AuxiliaryTree.hpp"
template <typename TREE>
std::pair<WeightedTree<int>, std::vector<int>>
auxiliary_tree(const HLD<TREE> &hld, std::vector<int> vs) {
assert(hld.prepared);
std::ranges::sort(vs, [&](int u, int v) { return hld.id[u] < hld.id[v]; });
std::vector<std::pair<int, int>> edges;
std::stack<int> sta;
sta.push(vs[0]);
for (int i = 0; i + 1 < vs.size(); i++) {
int w = hld.lca(vs[i], vs[i + 1]);
if (w != vs[i]) {
int l = sta.top();
sta.pop();
while (sta.size() and hld.T.depth[w] < hld.T.depth[sta.top()]) {
edges.emplace_back(sta.top(), l);
l = sta.top();
sta.pop();
}
if (sta.empty() or sta.top() != w)
sta.push(w);
edges.emplace_back(w, l);
}
sta.push(vs[i + 1]);
}
while (sta.size() > 1) {
int c = sta.top();
sta.pop();
edges.emplace_back(c, sta.top());
}
Compress<int> C;
for (const auto &[u, v] : edges)
C.add(u), C.add(v);
C.build();
WeightedTree<int> t(C.size());
for (const auto &[u, v] : edges)
t.add_edge(C[u], C[v], abs(hld.T.depth[u] - hld.T.depth[v]));
t.build();
std::vector<int> pre_vertex(C.size());
for (int i = 0; i < C.size(); i++)
pre_vertex[i] = C.r(i);
return std::make_pair(t, pre_vertex);
}
library/tree/AuxiliaryTree.hpp
build/pch/stdc++.hpp
library/graph/Graph.hpp