CP-Library
This documentation is automatically generated by online-judge-tools/verification-helper
graph/tree/HLD.hpp
- View this file on GitHub
- Last update: 2026-08-24 20:36:44+07:00
- Include:
#include "graph/tree/HLD.hpp"
Depends on
graph/Graph.hpp
Code
#pragma once
#include "graph/Graph.hpp"
template <typename T = int>
class HLD {
int n;
std::vector<int> parent, depth, sub, heavy, head, in, out;
int timer;
HLD(const Graph<T>& G, int root = 0) {
n = G.size();
parent.assign(n, -1);
depth.assign(n, 0);
sub.assign(n, 0);
heavy.assign(n, -1);
head.assign(n, 0);
in.assign(n, 0);
out.assign(n, 0);
timer = 0;
dfs_sz(G, root, -1, 0);
dfs_hld(G, root, -1, root);
}
void dfs_sz(const Graph<T>& G, int v, int p, int d) {
depth[v] = d;
parent[v] = p;
sub[v] = 1;
for (int u : G[v]) {
if (u != p) {
dfs_sz(G, u, v, d + 1);
sub[v] += sub[u];
if (heavy[v] == -1 || sub[u] > sub[heavy[v]]) {
heavy[v] = u;
}
}
}
}
void dfs_hld(const Graph<T>& G, int v, int p, int h) {
head[v] = h;
in[v] = timer++;
if (heavy[v] != -1) {
dfs_hld(G, heavy[v], v, h);
}
for (int u : G[v]) {
if (u != p && u != heavy[v]) {
dfs_hld(G, u, v, u);
}
}
out[v] = timer;
}
public:
int lca(int u, int v) const {
while (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
u = parent[head[u]];
}
return depth[u] < depth[v] ? u : v;
}
template <class F>
void path_query(int u, int v, bool is_edge, F f) const {
while (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
f(in[head[u]], in[u]);
u = parent[head[u]];
}
if (depth[u] > depth[v]) std::swap(u, v);
if (is_edge && u == v) return;
f(in[u] + (is_edge ? 1 : 0), in[v]);
}
template <class F>
void path_query_ordered(int u, int v, bool is_edge, F f) const {
std::vector<std::tuple<int, int, bool>> left, right;
while (head[u] != head[v]) {
if (depth[head[u]] >= depth[head[v]]) {
left.emplace_back(in[head[u]], in[u], true);
u = parent[head[u]];
} else {
right.emplace_back(in[head[v]], in[v], false);
v = parent[head[v]];
}
}
if (depth[u] >= depth[v]) {
int l = in[v] + (is_edge ? 1 : 0);
if (l <= in[u]) left.emplace_back(l, in[u], true);
} else {
int l = in[u] + (is_edge ? 1 : 0);
if (l <= in[v]) right.emplace_back(l, in[v], true);
}
for (auto [l, r, rev] : left) {
f(l, r, rev);
}
for (auto it = right.rbegin(); it != right.rend(); ++it) {
auto [l, r, rev] = *it;
f(l, r, rev);
}
}
template <class F>
void subtree_query(int v, bool is_edge, F f) const {
f(in[v] + (is_edge ? 1 : 0), out[v] - 1);
}
};#line 2 "graph/Graph.hpp"
#include <vector>
#include <cassert>
#include <utility>
template <typename T = int>
struct Edge {
int from, to;
T cost;
int id;
Edge() : from(-1), to(-1), cost(0), id(-1) {}
Edge(int _from, int _to, const T& _cost = 1, int _id = -1)
: from(_from), to(_to), cost(_cost), id(_id) {}
Edge(int _from, int _to, T&& _cost, int _id = -1)
: from(_from), to(_to), cost(std::move(_cost)), id(_id) {}
operator int() const { return to; }
friend bool operator<(const Edge<T>& lhs, const Edge<T>& rhs) {
return lhs.cost < rhs.cost;
}
friend bool operator>(const Edge<T>& lhs, const Edge<T>& rhs) {
return lhs.cost > rhs.cost;
}
};
template <typename T = int>
using Edges = std::vector<Edge<T>>;
template <typename T = int>
using GMatrix = std::vector<std::vector<T>>;
template <typename T = int>
struct Graph : std::vector<std::vector<Edge<T>>> {
using Base = std::vector<std::vector<Edge<T>>>;
using Base::Base;
int eid = 0;
int edge_size() const { return eid; }
int add_edge(int a, int b, const T& c = 1, bool is_directed = false) {
assert(0 <= a && a < (int)this->size());
assert(0 <= b && b < (int)this->size());
(*this)[a].emplace_back(a, b, c, eid);
if (!is_directed) {
(*this)[b].emplace_back(b, a, c, eid);
}
return eid++;
}
};
#line 3 "graph/tree/HLD.hpp"
template <typename T = int>
class HLD {
int n;
std::vector<int> parent, depth, sub, heavy, head, in, out;
int timer;
HLD(const Graph<T>& G, int root = 0) {
n = G.size();
parent.assign(n, -1);
depth.assign(n, 0);
sub.assign(n, 0);
heavy.assign(n, -1);
head.assign(n, 0);
in.assign(n, 0);
out.assign(n, 0);
timer = 0;
dfs_sz(G, root, -1, 0);
dfs_hld(G, root, -1, root);
}
void dfs_sz(const Graph<T>& G, int v, int p, int d) {
depth[v] = d;
parent[v] = p;
sub[v] = 1;
for (int u : G[v]) {
if (u != p) {
dfs_sz(G, u, v, d + 1);
sub[v] += sub[u];
if (heavy[v] == -1 || sub[u] > sub[heavy[v]]) {
heavy[v] = u;
}
}
}
}
void dfs_hld(const Graph<T>& G, int v, int p, int h) {
head[v] = h;
in[v] = timer++;
if (heavy[v] != -1) {
dfs_hld(G, heavy[v], v, h);
}
for (int u : G[v]) {
if (u != p && u != heavy[v]) {
dfs_hld(G, u, v, u);
}
}
out[v] = timer;
}
public:
int lca(int u, int v) const {
while (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
u = parent[head[u]];
}
return depth[u] < depth[v] ? u : v;
}
template <class F>
void path_query(int u, int v, bool is_edge, F f) const {
while (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
f(in[head[u]], in[u]);
u = parent[head[u]];
}
if (depth[u] > depth[v]) std::swap(u, v);
if (is_edge && u == v) return;
f(in[u] + (is_edge ? 1 : 0), in[v]);
}
template <class F>
void path_query_ordered(int u, int v, bool is_edge, F f) const {
std::vector<std::tuple<int, int, bool>> left, right;
while (head[u] != head[v]) {
if (depth[head[u]] >= depth[head[v]]) {
left.emplace_back(in[head[u]], in[u], true);
u = parent[head[u]];
} else {
right.emplace_back(in[head[v]], in[v], false);
v = parent[head[v]];
}
}
if (depth[u] >= depth[v]) {
int l = in[v] + (is_edge ? 1 : 0);
if (l <= in[u]) left.emplace_back(l, in[u], true);
} else {
int l = in[u] + (is_edge ? 1 : 0);
if (l <= in[v]) right.emplace_back(l, in[v], true);
}
for (auto [l, r, rev] : left) {
f(l, r, rev);
}
for (auto it = right.rbegin(); it != right.rend(); ++it) {
auto [l, r, rev] = *it;
f(l, r, rev);
}
}
template <class F>
void subtree_query(int v, bool is_edge, F f) const {
f(in[v] + (is_edge ? 1 : 0), out[v] - 1);
}
};