link_cut_tree¶
ソースコード¶
from titan_pylib.data_structures.dynamic_connectivity.link_cut_tree import LinkCutTree
展開済みコード¶
1# from titan_pylib.data_structures.dynamic_connectivity.link_cut_tree import LinkCutTree
2from array import array
3
4
5class LinkCutTree:
6 """LinkCutTree です。"""
7
8 # - link / cut / merge / split
9 # - root / same
10 # - lca / path_length / path_kth_elm
11 # など
12
13 def __init__(self, n: int) -> None:
14 self.n = n
15 self.arr: array[int] = array("I", [self.n, self.n, self.n, 0] * (self.n + 1))
16 # node.left : arr[node<<2|0]
17 # node.right : arr[node<<2|1]
18 # node.par : arr[node<<2|2]
19 # node.rev : arr[node<<2|3]
20 self.size: array[int] = array("I", [1] * (self.n + 1))
21 self.size[-1] = 0
22 self.group_cnt = self.n
23
24 def _is_root(self, node: int) -> bool:
25 return (self.arr[node << 2 | 2] == self.n) or not (
26 self.arr[self.arr[node << 2 | 2] << 2] == node
27 or self.arr[self.arr[node << 2 | 2] << 2 | 1] == node
28 )
29
30 def _propagate(self, node: int) -> None:
31 if node == self.n:
32 return
33 arr = self.arr
34 if arr[node << 2 | 3]:
35 arr[node << 2 | 3] = 0
36 ln, rn = arr[node << 2], arr[node << 2 | 1]
37 arr[node << 2] = rn
38 arr[node << 2 | 1] = ln
39 arr[ln << 2 | 3] ^= 1
40 arr[rn << 2 | 3] ^= 1
41
42 def _update(self, node: int) -> None:
43 if node == self.n:
44 return
45 ln, rn = self.arr[node << 2], self.arr[node << 2 | 1]
46 self._propagate(ln)
47 self._propagate(rn)
48 self.size[node] = 1 + self.size[ln] + self.size[rn]
49
50 def _update_triple(self, x: int, y: int, z: int) -> None:
51 self._propagate(self.arr[x << 2])
52 self._propagate(self.arr[x << 2 | 1])
53 self._propagate(self.arr[y << 2])
54 self._propagate(self.arr[y << 2 | 1])
55 self.size[z] = self.size[x]
56 self.size[x] = 1 + self.size[self.arr[x << 2]] + self.size[self.arr[x << 2 | 1]]
57 self.size[y] = 1 + self.size[self.arr[y << 2]] + self.size[self.arr[y << 2 | 1]]
58
59 def _update_double(self, x: int, y: int) -> None:
60 self._propagate(self.arr[x << 2])
61 self._propagate(self.arr[x << 2 | 1])
62 self.size[y] = self.size[x]
63 self.size[x] = 1 + self.size[self.arr[x << 2]] + self.size[self.arr[x << 2 | 1]]
64
65 def _splay(self, node: int) -> None:
66 # splayを抜けた後、nodeは遅延伝播済みにするようにする
67 # (splay後のnodeのleft,rightにアクセスしやすいと非常にラクなはず)
68 if node == self.n:
69 return
70 _propagate, _is_root, _update_triple = (
71 self._propagate,
72 self._is_root,
73 self._update_triple,
74 )
75 _propagate(node)
76 if _is_root(node):
77 return
78 arr = self.arr
79 pnode = arr[node << 2 | 2]
80 while not _is_root(pnode):
81 gnode = arr[pnode << 2 | 2]
82 _propagate(gnode)
83 _propagate(pnode)
84 _propagate(node)
85 f = arr[pnode << 2] == node
86 g = (arr[gnode << 2 | f] == pnode) ^ (arr[pnode << 2 | f] == node)
87 nnode = (node if g else pnode) << 2 | f ^ g
88 arr[pnode << 2 | f ^ 1] = arr[node << 2 | f]
89 arr[gnode << 2 | f ^ g ^ 1] = arr[nnode]
90 arr[node << 2 | f] = pnode
91 arr[nnode] = gnode
92 arr[node << 2 | 2] = arr[gnode << 2 | 2]
93 arr[gnode << 2 | 2] = nnode >> 2
94 arr[arr[pnode << 2 | f ^ 1] << 2 | 2] = pnode
95 arr[arr[gnode << 2 | f ^ g ^ 1] << 2 | 2] = gnode
96 arr[pnode << 2 | 2] = node
97 _update_triple(gnode, pnode, node)
98 pnode = arr[node << 2 | 2]
99 if arr[pnode << 2] == gnode:
100 arr[pnode << 2] = node
101 elif arr[pnode << 2 | 1] == gnode:
102 arr[pnode << 2 | 1] = node
103 else:
104 return
105 _propagate(pnode)
106 _propagate(node)
107 f = arr[pnode << 2] == node
108 arr[pnode << 2 | f ^ 1] = arr[node << 2 | f]
109 arr[node << 2 | f] = pnode
110 arr[arr[pnode << 2 | f ^ 1] << 2 | 2] = pnode
111 arr[node << 2 | 2] = arr[pnode << 2 | 2]
112 arr[pnode << 2 | 2] = node
113 self._update_double(pnode, node)
114
115 def expose(self, v: int) -> int:
116 """``v`` が属する木において、その木を管理しているsplay木の根から ``v`` までのパスを作ります。
117 償却 :math:`O(\\log{n})` です。
118 """
119 arr, n, _splay, _update = self.arr, self.n, self._splay, self._update
120 pre = v
121 while arr[v << 2 | 2] != n:
122 _splay(v)
123 arr[v << 2 | 1] = n
124 _update(v)
125 if arr[v << 2 | 2] == n:
126 break
127 pre = arr[v << 2 | 2]
128 _splay(pre)
129 arr[pre << 2 | 1] = v
130 _update(pre)
131 arr[v << 2 | 1] = n
132 _update(v)
133 return pre
134
135 def lca(self, u: int, v: int, root: int) -> int:
136 """``root`` を根としたときの、 ``u``, ``v`` の LCA を返します。
137 償却 :math:`O(\\log{n})` です。
138 """
139 self.evert(root)
140 self.expose(u)
141 return self.expose(v)
142
143 def link(self, c: int, p: int) -> None:
144 """辺 ``(c -> p)`` を追加します。
145 償却 :math:`O(\\log{n})` です。
146
147 制約:
148 ``c`` は元の木の根でなければならないです。
149 """
150 assert not self.same(c, p)
151 self.expose(c)
152 self.expose(p)
153 self.arr[c << 2 | 2] = p
154 self.arr[p << 2 | 1] = c
155 self._update(p)
156 self.group_cnt -= 1
157
158 def cut(self, c: int) -> None:
159 """辺 ``{c -> cの親}`` を削除します。
160 償却 :math:`O(\\log{n})` です。
161
162 制約:
163 ``c`` は元の木の根であってはいけないです。
164 """
165 arr = self.arr
166 self.expose(c)
167 assert arr[c << 2] != self.n
168 arr[arr[c << 2] << 2 | 2] = self.n
169 arr[c << 2] = self.n
170 self._update(c)
171 self.group_cnt += 1
172
173 def group_count(self) -> int:
174 """連結成分数を返します。
175 :math:`O(1)` です。
176 """
177 return self.group_cnt
178
179 def root(self, v: int) -> int:
180 """``v`` が属する木の根を返します。
181 償却 :math:`O(\\log{n})` です。
182 """
183 self.expose(v)
184 arr, n = self.arr, self.n
185 while arr[v << 2] != n:
186 v = arr[v << 2]
187 self._propagate(v)
188 self._splay(v)
189 return v
190
191 def same(self, u: int, v: int) -> bool:
192 """連結判定です。
193 償却 :math:`O(\\log{n})` です。
194
195 Returns:
196 bool: ``u``, ``v`` が同じ連結成分であれば ``True`` を、そうでなければ ``False`` を返します。
197 """
198 return self.root(u) == self.root(v)
199
200 def evert(self, v: int) -> None:
201 """``v`` を根にします。
202 償却 :math:`O(\\log{n})` です。
203 """
204 self.expose(v)
205 self.arr[v << 2 | 3] ^= 1
206 self._propagate(v)
207
208 def merge(self, u: int, v: int) -> bool:
209 """``u``, ``v`` が同じ連結成分なら ``False`` を返します。
210 そうでなければ辺 ``{u -> v}`` を追加して ``True`` を返します。
211 償却 :math:`O(\\log{n})` です。
212 """
213 if self.same(u, v):
214 return False
215 self.evert(u)
216 self.expose(v)
217 self.arr[u << 2 | 2] = v
218 self.arr[v << 2 | 1] = u
219 self._update(v)
220 self.group_cnt -= 1
221 return True
222
223 def split(self, u: int, v: int) -> bool:
224 """辺 ``{u -> v}`` があれば削除し ``True`` を返します。
225 そうでなければ何もせず ``False`` を返します。
226 償却 :math:`O(\\log{n})` です。
227 """
228 self.evert(u)
229 self.cut(v)
230 return True
231
232 def path_length(self, u: int, v: int) -> int:
233 """``u`` から ``v`` へのパスに含まれる頂点の数を返します。
234 存在しないときは ``-1`` を返します。
235 償却 :math:`O(\\log{n})` です。
236 """
237 if not self.same(u, v):
238 return -1
239 self.evert(u)
240 self.expose(v)
241 return self.size[v]
242
243 def path_kth_elm(self, s: int, t: int, k: int) -> int:
244 """``u`` から ``v`` へ ``k`` 個進んだ頂点を返します。
245 存在しないときは ``-1`` を返します。
246 償却 :math:`O(\\log{n})` です。
247 """
248 self.evert(s)
249 self.expose(t)
250 if self.size[t] <= k:
251 return -1
252 size, arr = self.size, self.arr
253 while True:
254 self._propagate(t)
255 s = size[arr[t << 2]]
256 if s == k:
257 self._splay(t)
258 return t
259 t = arr[t << 2 | (s < k)]
260 if s < k:
261 k -= s + 1
262
263 def __str__(self):
264 return f"{self.__class__.__name__}"
265
266 __repr__ = __str__
仕様¶
- class LinkCutTree(n: int)[source]¶
Bases:
objectLinkCutTree です。
- merge(u: int, v: int) bool[source]¶
u,vが同じ連結成分ならFalseを返します。 そうでなければ辺{u -> v}を追加してTrueを返します。 償却 \(O(\log{n})\) です。
- path_kth_elm(s: int, t: int, k: int) int[source]¶
uからvへk個進んだ頂点を返します。 存在しないときは-1を返します。 償却 \(O(\log{n})\) です。
- path_length(u: int, v: int) int[source]¶
uからvへのパスに含まれる頂点の数を返します。 存在しないときは-1を返します。 償却 \(O(\log{n})\) です。