perfect_binary_tree¶
ソースコード¶
from titan_pylib.graph.perfect_binary_tree import PerfectBinaryTree
展開済みコード¶
1# from titan_pylib.graph.perfect_binary_tree import PerfectBinaryTree
2class PerfectBinaryTree:
3 """1-indexedの完全二分木クラス"""
4
5 def __init__(self) -> None:
6 pass
7
8 def par(self, u: int) -> int:
9 """親を返す"""
10 return (u >> 1) if u > 1 else -1
11
12 def child_left(self, u: int) -> int:
13 """左の子を返す"""
14 return u << 1
15
16 def child_right(self, u: int) -> int:
17 """右の子を返す"""
18 return u << 1 | 1
19
20 def children(self, u: int) -> tuple[int, int]:
21 """左右の子をタプルで返す"""
22 return (self.child_left(u), self.child_right(u))
23
24 def sibling(self, u: int) -> int:
25 """兄弟を返す"""
26 return u ^ 1
27
28 def dep(self, u: int) -> int:
29 """深さを返す / :math:`O(1)`"""
30 return u.bit_length()
31
32 def la(self, u: int, k: int) -> int:
33 """``k``個上の祖先を返す
34 k == 0 のとき、u自身を返す
35 """
36 return u >> k
37
38 def lca(self, u: int, v: int) -> int:
39 """lcaを返す"""
40 if self.dep(u) > self.dep(v):
41 u, v = v, u
42 v = self.la(v, self.dep(v) - self.dep(u))
43 return u >> (u ^ v).bit_length()
44
45 def dist(self, u: int, v: int) -> int:
46 """距離を返す"""
47 return self.dep(u) + self.dep(v) - 2*self.dep(self.lca(u, v))
48
49 def get_path(self, u: int, v: int) -> list[int]:
50 """uからvへのパスをリストで返す"""
51 def get(x):
52 a = []
53 while x != lca:
54 a.append(x)
55 x = self.par(x)
56 return a
57
58 lca = self.lca(u, v)
59 return get(u) + [lca] + get(v)[::-1]