-
Notifications
You must be signed in to change notification settings - Fork 40
/
Copy pathHeavyLightDecomposition.h
125 lines (122 loc) · 6.16 KB
/
HeavyLightDecomposition.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/*
最后修改:
20240429
测试环境:
gcc11.2,c++11
clang12.0,C++11
msvc14.2,C++14
*/
#ifndef __OY_HEAVYLIGHTDECOMPOSITION__
#define __OY_HEAVYLIGHTDECOMPOSITION__
#include <algorithm>
#include <cstdint>
#include <functional>
#include <numeric>
#include <vector>
namespace OY {
namespace HLD {
using size_type = uint32_t;
template <typename Tree>
struct Table {
struct node {
size_type m_top_dfn, m_top_dep, m_parent, m_dfn, m_dep, m_size, m_heavy;
};
Tree *m_rooted_tree;
std::vector<node> m_info;
std::vector<size_type> m_seq;
void _tree_dfs1(size_type a, size_type p) {
m_info[a].m_size = 1, m_info[a].m_heavy = -1;
m_rooted_tree->do_for_each_adj_vertex(a, [&](size_type to) {
if (to != p) {
_tree_dfs1(to, a);
size_type to_size = m_info[to].m_size;
m_info[a].m_size += to_size;
if (!~m_info[a].m_heavy || to_size > m_info[m_info[a].m_heavy].m_size) m_info[a].m_heavy = to;
}
});
}
void _tree_dfs2(size_type a, size_type p, size_type &cursor) {
m_seq[cursor] = a;
if (~p) m_info[a].m_dep = m_info[p].m_dep + 1;
m_info[a].m_dfn = cursor++;
bool is_top = !~p || a != m_info[p].m_heavy;
m_info[a].m_top_dfn = is_top ? m_info[a].m_dfn : m_info[p].m_top_dfn;
m_info[a].m_top_dep = is_top ? m_info[a].m_dep : m_info[p].m_top_dep;
m_info[a].m_parent = is_top ? p : m_info[p].m_parent;
size_type heavy = m_info[a].m_heavy;
if (~heavy) _tree_dfs2(heavy, a, cursor);
m_rooted_tree->do_for_each_adj_vertex(a, [&](size_type to) { if (to != p && to != heavy) _tree_dfs2(to, a, cursor); });
}
Table(Tree *rooted_tree = nullptr) { reset(rooted_tree); }
void reset(Tree *rooted_tree) {
if (!(m_rooted_tree = rooted_tree)) return;
m_info.resize(m_rooted_tree->vertex_cnt()), m_seq.resize(m_rooted_tree->vertex_cnt());
_tree_dfs1(m_rooted_tree->m_root, -1);
size_type cursor = 0;
_tree_dfs2(m_rooted_tree->m_root, -1, cursor);
}
size_type get_ancestor(size_type a, size_type n) const {
auto info = m_info.data();
if (n > info[a].m_dep) return -1;
size_type dep = info[a].m_dep, target_dep = dep - n;
while (target_dep < info[a].m_top_dep) dep = info[a].m_top_dep - 1, a = info[a].m_parent;
return m_seq[info[a].m_dfn - dep + target_dep];
}
size_type find_parent(size_type a) const { return m_info[a].m_top_dep == m_info[a].m_dep ? m_info[a].m_parent : (m_info[a].m_dfn ? m_seq[m_info[a].m_dfn - 1] : -1); }
size_type find_son(size_type a, size_type b) const { return get_ancestor(b, m_info[b].m_dep - m_info[a].m_dep - 1); }
size_type get_depth(size_type a) const { return m_info[a].m_dep; }
template <typename Callback>
auto do_for_vertex(size_type a, Callback &&call) const -> decltype(call(0)) { return call(m_info[a].m_dfn); }
template <bool LCA, typename Callback>
void do_for_path(size_type a, size_type b, Callback &&call) const {
auto info = m_info.data();
while (info[a].m_top_dfn != info[b].m_top_dfn)
if (info[a].m_top_dep < info[b].m_top_dep)
call(info[b].m_top_dfn, info[b].m_dfn), b = info[b].m_parent;
else
call(info[a].m_top_dfn, info[a].m_dfn), a = info[a].m_parent;
if (info[a].m_dep > info[b].m_dep) std::swap(a, b);
if constexpr (LCA)
call(info[a].m_dfn, info[b].m_dfn);
else if (a != b)
call(info[a].m_dfn + 1, info[b].m_dfn);
}
template <bool LCA, typename Callback>
void do_for_off_path(size_type a, size_type b, Callback &&call) const {
std::pair<size_type, size_type> ranges[32];
size_type cnt = 0;
do_for_path<LCA>(a, b, [&](size_type l, size_type r) { ranges[cnt++] = {l, r}; });
if (!cnt) return;
std::sort(ranges, ranges + cnt);
if (ranges[0].first) call(0, ranges[0].first - 1);
for (size_type i = 1; i != cnt; i++)
if (ranges[i - 1].second + 1 != ranges[i].first) call(ranges[i - 1].second + 1, ranges[i].first - 1);
if (ranges[cnt - 1].second + 1 != m_rooted_tree->vertex_cnt()) call(ranges[cnt - 1].second + 1, m_rooted_tree->vertex_cnt() - 1);
}
template <typename Callback>
void do_for_directed_path(size_type from, size_type to, Callback &&call) const {
auto info = m_info.data();
while (info[from].m_top_dfn != info[to].m_top_dfn)
if (info[from].m_top_dep < info[to].m_top_dep) {
do_for_directed_path(from, info[to].m_parent, call);
call(info[to].m_top_dfn, info[to].m_dfn);
return;
} else
call(info[from].m_dfn, info[from].m_top_dfn), from = info[from].m_parent;
call(info[from].m_dfn, info[to].m_dfn);
}
template <typename Callback>
auto do_for_subtree(size_type a, Callback &&call) const -> decltype(call(0, 0)) { return call(m_info[a].m_dfn, m_info[a].m_dfn + m_info[a].m_size - 1); }
size_type calc(size_type a, size_type b) const {
auto info = m_info.data();
while (info[a].m_top_dfn != info[b].m_top_dfn)
if (info[a].m_top_dep < info[b].m_top_dep)
b = info[b].m_parent;
else
a = info[a].m_parent;
return info[a].m_dep < info[b].m_dep ? a : b;
}
};
}
}
#endif