GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 98.6% 70 / 0 / 71
Functions: 100.0% 20 / 0 / 20
Branches: 86.1% 31 / 0 / 36
src/ds/link_cut_tree/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../util/alias/others/lib.hpp"
4
5 namespace tifa_libs {
6
7 template <class T, auto op, auto inv_op>
8 requires requires(T x, T y) {
9 { op(x, y) } -> std::same_as<T>;
10 { inv_op(x, y) } -> std::same_as<T>;
11 }
12 class link_cut_tree {
13 // function in private: index of node should start from 1
14 // wait for updating
15 struct TIFA {
16 T w, val;
17 T s, sv; // requirement of maintaining subtree
18 u32 fa, rev;
19 arr<u32, 2> son;
20 };
21
22 public:
23 vec<TIFA> tr;
24
25 102 CEXP link_cut_tree(u32 n, vec<T> A) NE : tr(n + 1) {
26
2/2
✓ Branch 2 taken 5551796 times.
✓ Branch 3 taken 51 times.
 5551847 flt_ (u32, i, 1, n + 1) tr[i].val = A[i - 1];
27 51 }
28
29 CEXP void access(u32 x) NE { access_(x + 1); }
30 CEXP void makeroot(u32 x) NE { makeroot_(x + 1); }
31 CEXP u32 findroot(u32 x) NE { return findroot_(x + 1) - 1; }
32 CEXP void split(u32 x, u32 y) NE { split_(x + 1, y + 1); }
33 CEXP bool con(u32 x, u32 y) NE { return con_(x + 1, y + 1); }
34 7366068 CEXP bool link(u32 x, u32 y) NE { return link_(x + 1, y + 1); }
35 1814323 CEXP bool cut(u32 x, u32 y) NE { return cut_(x + 1, y + 1); }
36 CEXP void node_update(u32 x, T k) NE {
37 x += 1;
38 access_(x); // requirement of maintaining subtree
39 splay_(x), tr[x].val = k, update_(x);
40 }
41 1812606 CEXP void node_add(u32 x, T k) NE {
42 1812606 x += 1;
43 1812606 access_(x); // requirement of maintaining subtree
44 1812606 splay_(x), tr[x].val = op(tr[x].val, k), update_(x);
45 1812606 }
46 CEXP u32 lca(u32 u, u32 v, u32 root = 0) NE {
47 if (u == v) return u;
48 ++u, ++v, ++root, makeroot_(root), access_(u);
49 u32 ret = access_(v) - 1;
50 retif_((tr[u].fa), ret, -1u);
51 }
52 1297224 CEXP ptt<T> query_subtree(u32 x, u32 y) NE {
53 1297224 split_(++x, ++y);
54 1297224 return {op(tr[x].sv, tr[x].val), op(tr[y].sv, tr[y].val)};
55 }
56 714273 CEXP T query_path(u32 x, u32 y) NE {
57 714273 split_(++x, ++y);
58 714273 return tr[y].w;
59 }
60
61 private:
62 442610454 CEXP void update_(u32 x) NE {
63 442610454 tr[x].w = op(op(tr[tr[x].son[0]].w, tr[x].val), tr[tr[x].son[1]].w);
64 442610454 tr[x].s = op(op(op(tr[tr[x].son[0]].s, tr[x].val), tr[tr[x].son[1]].s), tr[x].sv); // requirement of maintaining subtree
65 442610454 }
66 642787142 CEXP bool which_(u32 x) NE { return tr[tr[x].fa].son[1] == x; }
67
4/4
✓ Branch 3 taken 689671229 times.
✓ Branch 4 taken 263700133 times.
✓ Branch 8 taken 335209969 times.
✓ Branch 9 taken 354461260 times.
 953371362 CEXP bool noroot_(u32 x) NE { return tr[tr[x].fa].son[0] == x || tr[tr[x].fa].son[1] == x; }
68 163130212 CEXP void all_update_(u32 x) NE {
69
2/2
✓ Branch 0 taken 119285484 times.
✓ Branch 1 taken 43844728 times.
 163130212 if (x) swap(tr[x].son[0], tr[x].son[1]), tr[x].rev ^= 1;
70 163130212 }
71 341941386 CEXP void pushdown_(u32 x) NE {
72
2/2
✓ Branch 1 taken 75969162 times.
✓ Branch 2 taken 265972224 times.
 341941386 if (tr[x].rev) all_update_(tr[x].son[0]), all_update_(tr[x].son[1]), tr[x].rev ^= 1;
73 341941386 }
74 341941386 CEXP void ppushdown_(u32 x) NE {
75
2/2
✓ Branch 1 taken 228068933 times.
✓ Branch 2 taken 113872453 times.
 341941386 if (noroot_(x)) ppushdown_(tr[x].fa);
76 341941386 pushdown_(x);
77 341941386 }
78 228068933 CEXP void rotate(u32 x) NE {
79 228068933 cu32 y = tr[x].fa, z = tr[y].fa, y_son = which_(x), z_son = which_(y), B = tr[x].son[y_son ^ 1];
80
2/2
✓ Branch 1 taken 142772236 times.
✓ Branch 2 taken 85296697 times.
 228068933 if (noroot_(y)) tr[z].son[z_son] = x;
81
2/2
✓ Branch 4 taken 161020073 times.
✓ Branch 5 taken 67048860 times.
 228068933 if (tr[x].fa = z, tr[y].fa = x, tr[x].son[y_son ^ 1] = y; B) tr[B].fa = y;
82 228068933 tr[y].son[y_son] = B, update_(y);
83 228068933 }
84 113872453 CEXP void splay_(u32 x) NE {
85 113872453 ppushdown_(x);
86
2/2
✓ Branch 1 taken 134744295 times.
✓ Branch 2 taken 113872453 times.
 248616748 while (noroot_(x)) {
87
2/2
✓ Branch 2 taken 93324638 times.
✓ Branch 3 taken 41419657 times.
 134744295 if (cu32 fa = tr[x].fa; noroot_(fa)) {
88
2/2
✓ Branch 2 taken 27404314 times.
✓ Branch 3 taken 65920324 times.
 93324638 if (which_(fa) ^ which_(x)) rotate(x);
89 65920324 else rotate(fa);
90 }
91 134744295 rotate(x);
92 }
93 113872453 update_(x);
94 113872453 }
95 24196382 CEXP u32 access_(u32 x) NE {
96 24196382 u32 y = 0;
97
2/2
✓ Branch 1 taken 89676071 times.
✓ Branch 2 taken 24196382 times.
 113872453 for (; x; x = tr[y = x].fa) {
98 89676071 splay_(x);
99 89676071 tr[x].sv = inv_op(op(tr[x].sv, tr[tr[x].son[1]].s), tr[y].s); // requirement of maintaining subtree
100 89676071 tr[x].son[1] = y, update_(x);
101 }
102 24196382 return y;
103 }
104 11191888 CEXP void makeroot_(u32 x) NE { access_(x), splay_(x), all_update_(x); }
105 9180391 CEXP u32 findroot_(u32 x) NE {
106 9180391 access_(x), splay_(x);
107
2/2
✓ Branch 4 taken 3314271 times.
✓ Branch 5 taken 9180391 times.
 12494662 while (tr[x].son[0]) x = tr[x].son[0];
108 9180391 return x;
109 }
110 2011497 CEXP void split_(u32 x, u32 y) NE { makeroot_(x), access_(y), splay_(y); }
111 CEXP bool con_(u32 x, u32 y) NE {
112 makeroot_(x);
113 if (findroot_(y) != x) return true;
114 return false;
115 }
116 7366068 CEXP bool link_(u32 x, u32 y) NE {
117 7366068 makeroot_(x);
118
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 7366068 times.
 7366068 if (findroot_(y) == x) return false;
119 7366068 tr[y].sv = op(tr[y].sv, tr[x].s); // requirement of maintaining subtree
120 7366068 tr[x].fa = y, update_(y);
121 7366068 return true;
122 }
123 1814323 CEXP bool cut_(u32 x, u32 y) NE {
124
4/8
✓ Branch 2 taken 1814323 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1814323 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 1814323 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 1814323 times.
✗ Branch 12 not taken.
 1814323 if (makeroot_(x); findroot_(y) == x && tr[x].fa == y && tr[y].son[0] == x) {
125 1814323 tr[y].son[0] = tr[x].fa = 0, update_(y);
126 1814323 return true;
127 }
128 ✗ return false;
129 }
130 };
131
132 } // namespace tifa_libs
133