GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 66.4% 73 / 0 / 110
Functions: 35.7% 5 / 0 / 14
Branches: 39.0% 57 / 36 / 182
static_tree.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "yc.hpp"
4 #include "rmq.hpp"
5
6 struct static_forest_t {
7 int N;
8
9 private:
10 // original label to preorder
11 std::vector<int> idx;
12
13 // all keys/values are by preorder relabelling
14 std::vector<int> preorder;
15 std::vector<int> depth;
16 std::vector<int> par;
17 std::vector<int> sz;
18 std::vector<int> heavy_par;
19 std::vector<int> heavy_dist;
20
21 std::vector<int> depth_val_to_idx;
22 RangeMinQuery<int> depth_val_rmq;
23
24 public:
25
26 ✗ static_forest_t() : N(0) {}
27
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 25 times.
 25 static_forest_t(const std::vector<std::vector<int>>& adj, const std::vector<int>& roots = {}) :
28 25 N(int(adj.size())),
29
1/1
✓ Branch 5 → 6 taken 25 times.
 25 idx(N, -1),
30
2/3
✓ Branch 5 → 6 taken 25 times.
✓ Branch 6 → 7 taken 25 times.
✗ Branch 9 → 10 not taken.
 25 preorder(N, -1),
31
2/3
✓ Branch 6 → 7 taken 25 times.
✓ Branch 7 → 8 taken 25 times.
✗ Branch 13 → 14 not taken.
 25 depth(N, -1),
32
2/3
✓ Branch 7 → 8 taken 25 times.
✓ Branch 8 → 9 taken 25 times.
✗ Branch 17 → 18 not taken.
 25 par(N, -1),
33
2/3
✓ Branch 8 → 9 taken 25 times.
✓ Branch 9 → 10 taken 25 times.
✗ Branch 21 → 22 not taken.
 25 sz(N, -1),
34
2/3
✓ Branch 9 → 10 taken 25 times.
✓ Branch 10 → 11 taken 25 times.
✗ Branch 25 → 26 not taken.
 25 heavy_par(N, -1),
35
2/3
✓ Branch 10 → 11 taken 25 times.
✓ Branch 11 → 12 taken 25 times.
✗ Branch 29 → 30 not taken.
 25 heavy_dist(N, -1),
36
2/3
✓ Branch 11 → 12 taken 25 times.
✓ Branch 12 → 13 taken 25 times.
✗ Branch 33 → 34 not taken.
 25 depth_val_to_idx(N, -1)
37 {
38 25 {
39 25 int nxt_idx = 0;
40
2/3
✓ Branch 12 → 13 taken 25 times.
✓ Branch 13 → 14 taken 25 times.
✗ Branch 38 → 39 not taken.
 25 std::vector<int> depth_freq(N, 0);
41
2/3
✓ Branch 13 → 14 taken 25 times.
✓ Branch 14 → 15 taken 25 times.
✗ Branch 42 → 43 not taken.
 25 std::vector<int> depth_val(N, -1);
42
2/4
✓ Branch 14 → 15 taken 25 times.
✓ Branch 15 → 18 taken 25 times.
✗ Branch 15 → 22 not taken.
✗ Branch 46 → 47 not taken.
 25 std::vector<int> heavy_child(N, -1);
43 50 auto build_one_tree = [&](int rt) -> void {
44
0/1
✗ Branch 2 → 3 not taken.
 10224977 std::y_combinator([&](auto self, int cur, int prv) -> int {
45 10224927 int cur_sz = 1;
46 10224927 int cur_heavy = -1;
47 10224927 int cur_heavy_weight = 0;
48
2/4
✓ Branch 10 → 3 taken 20449804 times.
✓ Branch 10 → 11 taken 10224927 times.
✗ Branch 22 → 5 not taken.
✗ Branch 22 → 23 not taken.
 30674731 for (int nxt : adj[cur]) {
49
2/4
✓ Branch 3 → 4 taken 10224902 times.
✓ Branch 3 → 5 taken 10224902 times.
✗ Branch 7 → 8 not taken.
✗ Branch 7 → 9 not taken.
 20449804 if (nxt == prv) continue;
50
0/1
✗ Branch 9 → 10 not taken.
 10224902 int n_sz = self(nxt, cur);
51
2/4
✓ Branch 6 → 7 taken 7921998 times.
✓ Branch 6 → 8 taken 2302904 times.
✗ Branch 10 → 11 not taken.
✗ Branch 10 → 12 not taken.
 10224902 if (n_sz > cur_heavy_weight) {
52 7921998 cur_heavy = nxt;
53 7921998 cur_heavy_weight = n_sz;
54 }
55 10224902 cur_sz += n_sz;
56 }
57 10224927 heavy_child[cur] = cur_heavy;
58 10224927 return cur_sz;
59
0/1
✗ Branch 3 → 4 not taken.
 25 })(rt, -1);
60 25 assert(idx[rt] == -1);
61
0/1
✗ Branch 7 → 8 not taken.
 10224977 std::y_combinator([&](auto&& self, int cur, int prv, int par_idx, int d, bool is_heavy_root) -> void {
62
2/2
✓ Branch 2 → 3 taken 10224902 times.
✓ Branch 2 → 5 taken 25 times.
 10224927 int cur_idx = idx[cur] = nxt_idx++;
63 10224927 preorder[cur_idx] = cur;
64 10224927 par[cur_idx] = par_idx;
65 10224927 depth[cur_idx] = d;
66 10224927 depth_val[cur_idx] = ++depth_freq[d];
67 17769323 assert(is_heavy_root == (par_idx == -1 || cur_idx != par_idx + 1));
68
2/4
✓ Branch 7 → 8 taken 2680531 times.
✓ Branch 7 → 9 taken 7544396 times.
✗ Branch 14 → 15 not taken.
✗ Branch 14 → 18 not taken.
 10224927 if (is_heavy_root) {
69 2680531 heavy_par[cur_idx] = par_idx;
70 2680531 heavy_dist[cur_idx] = 1;
71 } else {
72 7544396 assert(par_idx == cur_idx - 1);
73 7544396 heavy_par[cur_idx] = heavy_par[cur_idx - 1];
74 7544396 heavy_dist[cur_idx] = heavy_dist[cur_idx - 1] + 1;
75 }
76
2/4
✓ Branch 12 → 13 taken 7544396 times.
✓ Branch 12 → 15 taken 2680531 times.
✗ Branch 26 → 27 not taken.
✗ Branch 26 → 30 not taken.
 10224927 if (heavy_child[cur] != -1) {
77 7544396 int nxt = heavy_child[cur];
78
0/1
✗ Branch 28 → 29 not taken.
 7544396 self(nxt, cur, cur_idx, d+1, false);
79 }
80
2/4
✓ Branch 23 → 16 taken 20449804 times.
✓ Branch 23 → 24 taken 10224927 times.
✗ Branch 51 → 33 not taken.
✗ Branch 51 → 52 not taken.
 30674731 for (int nxt : adj[cur]) {
81
2/4
✓ Branch 16 → 17 taken 10224902 times.
✓ Branch 16 → 18 taken 10224902 times.
✗ Branch 35 → 36 not taken.
✗ Branch 35 → 37 not taken.
 20449804 if (nxt == prv) continue;
82
2/4
✓ Branch 18 → 19 taken 7544396 times.
✓ Branch 18 → 20 taken 2680506 times.
✗ Branch 38 → 39 not taken.
✗ Branch 38 → 40 not taken.
 10224902 if (nxt == heavy_child[cur]) continue;
83
0/1
✗ Branch 40 → 41 not taken.
 2680506 self(nxt, cur, cur_idx, d+1, true);
84 }
85 10224927 sz[cur_idx] = nxt_idx - cur_idx;
86
0/1
✗ Branch 8 → 9 not taken.
 25 })(rt, -1, -1, 0, true);
87 50 };
88
1/4
✓ Branch 15 → 18 taken 25 times.
✗ Branch 15 → 22 not taken.
✗ Branch 49 → 50 not taken.
✗ Branch 49 → 66 not taken.
 25 if (!roots.empty()) {
89
3/6
✓ Branch 16 → 17 taken 25 times.
✓ Branch 18 → 16 taken 25 times.
✓ Branch 18 → 26 taken 25 times.
✗ Branch 54 → 55 not taken.
✗ Branch 64 → 52 not taken.
✗ Branch 64 → 65 not taken.
 50 for (int r : roots) build_one_tree(r);
90 } else {
91 ✗ for (int rt = 0; rt < N; rt++) {
92 ✗ if (idx[rt] == -1) {
93 ✗ build_one_tree(rt);
94 }
95 }
96 }
97
2/4
✓ Branch 27 → 23 taken 10224927 times.
✓ Branch 27 → 29 taken 25 times.
✗ Branch 77 → 73 not taken.
✗ Branch 77 → 78 not taken.
 10224952 for (int i = 0; i < N; i++) {
98 10224927 assert(idx[i] != -1);
99 }
100
2/4
✓ Branch 29 → 28 taken 10224902 times.
✓ Branch 29 → 33 taken 25 times.
✗ Branch 82 → 79 not taken.
✗ Branch 82 → 83 not taken.
 10224927 for (int i = 1; i < N; i++) {
101 10224902 depth_freq[i] += depth_freq[i-1];
102 }
103
2/4
✓ Branch 33 → 30 taken 10224927 times.
✓ Branch 33 → 34 taken 25 times.
✗ Branch 95 → 84 not taken.
✗ Branch 95 → 96 not taken.
 10224952 for (int i = 0; i < N; i++) {
104
1/2
✗ Branch 30 → 31 not taken.
✓ Branch 30 → 32 taken 10224927 times.
 10224927 depth_val[i] = depth_freq[depth[i]] - depth_val[i];
105 10224927 assert(depth_val_to_idx[depth_val[i]] == -1);
106 10224927 depth_val_to_idx[depth_val[i]] = i;
107 }
108
1/2
✓ Branch 34 → 35 taken 25 times.
✗ Branch 96 → 97 not taken.
 25 depth_val_rmq = RangeMinQuery<int>(depth_val);
109 25 }
110 25 }
111
112 ✗ int dist(int a, int b) const {
113 ✗ if (a == b) return 0;
114 ✗ a = idx[a], b = idx[b];
115 ✗ if (a > b) std::swap(a, b);
116 ✗ int o = depth_val_to_idx[depth_val_rmq.query(a+1, b)];
117 ✗ return depth[a] + depth[b] - 2 * (depth[o] - 1);
118 }
119
120 9662271 int lca(int a, int b) const {
121
1/3
✓ Branch 2 → 3 taken 9662271 times.
✗ Branch 2 → 4 not taken.
✗ Branch 2 → 7 not taken.
 9662271 if (a == b) return a;
122
2/2
✓ Branch 3 → 4 taken 4222685 times.
✓ Branch 3 → 5 taken 5439586 times.
 9662271 a = idx[a], b = idx[b];
123
2/4
✓ Branch 3 → 4 taken 4222685 times.
✓ Branch 3 → 5 taken 5439586 times.
✗ Branch 6 → 7 not taken.
✗ Branch 6 → 8 not taken.
 9662271 if (a > b) std::swap(a, b);
124 9662271 int o = depth_val_to_idx[depth_val_rmq.query(a+1, b)];
125 9662271 return preorder[par[o]];
126 }
127
128 // query which subtree of a contains b; b must be inside a
129 // returns -1 if a == b
130 ✗ int get_subtree(int a, int b) const {
131 ✗ if (a == b) return -1;
132 ✗ a = idx[a], b = idx[b];
133 ✗ assert(a < b && b < a + sz[a]);
134 ✗ return preorder[depth_val_to_idx[depth_val_rmq.query(a+1, b)]];
135 }
136
137 // next from a to b, a and b must be in the same tree
138 ✗ int get_next(int a, int b) const {
139 ✗ if (a == b) return -1;
140 ✗ a = idx[a], b = idx[b];
141 ✗ if (a < b && b < a + sz[a]) {
142 ✗ return preorder[depth_val_to_idx[depth_val_rmq.query(a+1, b)]];
143 } else {
144 ✗ return preorder[par[a]];
145 }
146 }
147
148 ✗ int get_ancestor(int a, int k) const {
149 ✗ assert(k >= 0);
150 ✗ a = idx[a];
151 ✗ if (k > depth[a]) return -1;
152 ✗ while (a != -1 && k > 0) {
153 ✗ if (k >= heavy_dist[a]) {
154 ✗ k -= heavy_dist[a];
155 ✗ assert(heavy_par[a] <= a - heavy_dist[a]);
156 ✗ a = heavy_par[a];
157 } else {
158 ✗ a -= k;
159 ✗ k = 0;
160 }
161 }
162 ✗ return preorder[a];
163 }
164
165 ✗ int get_depth(int a) const { return depth[idx[a]]; }
166 ✗ int get_sz(int a) const { return sz[idx[a]]; }
167 ✗ std::array<int, 2> get_range(int a) const { return {idx[a], idx[a] + sz[idx[a]]}; }
168 ✗ bool is_ancestor(int a, int b) { return idx[a] <= idx[b] && idx[b] < idx[a] + sz[idx[a]]; }
169 };
170