link cut tree¶
ソースコード¶
1#include <vector>
2#include <cassert>
3using namespace std;
4
5// LinkCutTree
6namespace titan23 {
7
8 class LinkCutTree {
9 private:
10 struct Node;
11 using NodePtr = Node*;
12 vector<NodePtr> pool;
13
14 struct Node {
15 int index, size, rev;
16 NodePtr left, right, par;
17
18 Node(const int index) :
19 index(index), size(1), rev(0),
20 left(nullptr), right(nullptr), par(nullptr) {
21 }
22
23 bool is_root() const {
24 return (!par) || (!(par->left == this || par->right == this));
25 }
26 };
27
28 void _apply_rev(const NodePtr node) {
29 if (!node) return;
30 node->rev ^= 1;
31 }
32
33 void _propagate(const NodePtr node) {
34 if (!node) return;
35 if (node->rev) {
36 swap(node->left, node->right);
37 _apply_rev(node->left);
38 _apply_rev(node->right);
39 node->rev = 0;
40 }
41 }
42
43 void _update(const NodePtr node) {
44 if (!node) return;
45 _propagate(node->left);
46 _propagate(node->right);
47 node->size = 1;
48 if (node->left) {
49 node->size += node->left->size;
50 }
51 if (node->right) {
52 node->size += node->right->size;
53 }
54 }
55
56 void _rotate(const NodePtr node) {
57 const NodePtr pnode = node->par;
58 const NodePtr gnode = pnode->par;
59 _propagate(pnode);
60 _propagate(node);
61 if (gnode) {
62 if (gnode->left == pnode) {
63 gnode->left = node;
64 } else if (gnode->right == pnode) {
65 gnode->right = node;
66 }
67 }
68 node->par = gnode;
69 if (pnode->left == node) {
70 pnode->left = node->right;
71 if (node->right) node->right->par = pnode;
72 node->right = pnode;
73 } else {
74 pnode->right = node->left;
75 if (node->left) node->left->par = pnode;
76 node->left = pnode;
77 }
78 pnode->par = node;
79 _update(pnode);
80 _update(node);
81 }
82
83 void _splay(const NodePtr node) {
84 while ((!node->is_root()) && (!node->par->is_root())) {
85 if ((node->par->par->left == node->par) == (node->par->left == node)) {
86 _rotate(node->par);
87 } else {
88 _rotate(node);
89 }
90 _rotate(node);
91 }
92 if (!node->is_root()) _rotate(node);
93 _propagate(node);
94 }
95
96 void _link(const NodePtr c, const NodePtr p) {
97 _expose(c);
98 _expose(p);
99 c->par = p;
100 p->right = c;
101 _update(p);
102 }
103
104 void _cut(const NodePtr c) {
105 _expose(c);
106 c->left->par = nullptr;
107 c->left = nullptr;
108 _update(c);
109 }
110
111 NodePtr _expose(const NodePtr node) {
112 NodePtr pre = node;
113 while (node->par) {
114 _splay(node);
115 node->right = nullptr;
116 _update(node);
117 if (!node->par) break;
118 pre = node->par;
119 _splay(node->par);
120 node->par->right = node;
121 _update(node->par);
122 }
123 node->right = nullptr;
124 _update(node);
125 return pre;
126 }
127
128 NodePtr _root(NodePtr v) {
129 _expose(v);
130 _propagate(v);
131 while (v->left) {
132 v = v->left;
133 _propagate(v);
134 }
135 _splay(v);
136 return v;
137 }
138
139 void _evert(NodePtr v) {
140 _expose(v);
141 _apply_rev(v);
142 _propagate(v);
143 }
144
145 public:
146 LinkCutTree() {}
147
148 LinkCutTree(int n) {
149 pool.resize(n);
150 for (int i = 0; i < n; ++i) {
151 pool[i] = new Node(i);
152 }
153 }
154
155 int expose(int v) {
156 return _expose(pool[v])->index;
157 }
158
159 int lca(int u, int v, int root=-1) {
160 if (root != -1) evert(root);
161 expose(u);
162 return expose(v);
163 }
164
165 void link(int c, int p) {
166 _link(pool[c], pool[p]);
167 }
168
169 void cut(int c) {
170 _cut(pool[c]);
171 }
172
173 int root(int v) {
174 return _root(pool[v])->index;
175 }
176
177 bool same(int u, int v) {
178 return root(u) == root(v);
179 }
180
181 void evert(int v) {
182 _evert(pool[v]);
183 }
184
185 bool merge(int u, int v) {
186 if (same(u, v)) return false;
187 evert(u);
188 link(u, v);
189 return true;
190 }
191
192 void split(int u, int v) {
193 evert(u);
194 cut(v);
195 }
196
197 int path_kth_elm(int s, int t, int k) {
198 evert(s);
199 expose(t);
200 NodePtr node = pool[t];
201 if (node->size <= k) return -1;
202 while (true) {
203 _propagate(node);
204 t = node->left? node->left->size: 0;
205 if (t == k) {
206 _splay(node);
207 return node->index;
208 }
209 if (t > k) {
210 node = node->left;
211 } else {
212 node = node->right;
213 k -= t + 1;
214 }
215 }
216 }
217 };
218} // namespace titan23
仕様¶
Warning
doxygenfile: Cannot find file “titan_cpplib/data_structures/link_cut_tree.cpp