Source code for titan_pylib.graph.perfect_binary_tree


[docs]
 1class PerfectBinaryTree:
 2    """1-indexedの完全二分木クラス"""
 3
 4    def __init__(self) -> None:
 5        pass
 6

[docs]
 7    def par(self, u: int) -> int:
 8        """親を返す"""
 9        return (u >> 1) if u > 1 else -1

10

[docs]
11    def child_left(self, u: int) -> int:
12        """左の子を返す"""
13        return u << 1

14

[docs]
15    def child_right(self, u: int) -> int:
16        """右の子を返す"""
17        return u << 1 | 1

18

[docs]
19    def children(self, u: int) -> tuple[int, int]:
20        """左右の子をタプルで返す"""
21        return (self.child_left(u), self.child_right(u))

22

[docs]
23    def sibling(self, u: int) -> int:
24        """兄弟を返す"""
25        return u ^ 1

26

[docs]
27    def dep(self, u: int) -> int:
28        """深さを返す / :math:`O(1)`"""
29        return u.bit_length()

30

[docs]
31    def la(self, u: int, k: int) -> int:
32        """``k``個上の祖先を返す
33        k == 0 のとき、u自身を返す
34        """
35        return u >> k

36

[docs]
37    def lca(self, u: int, v: int) -> int:
38        """lcaを返す"""
39        if self.dep(u) > self.dep(v):
40            u, v = v, u
41        v = self.la(v, self.dep(v) - self.dep(u))
42        return u >> (u ^ v).bit_length()

43    

[docs]
44    def dist(self, u: int, v: int) -> int:
45        """距離を返す"""
46        return self.dep(u) + self.dep(v) - 2*self.dep(self.lca(u, v))

47

[docs]
48    def get_path(self, u: int, v: int) -> list[int]:
49        """uからvへのパスをリストで返す"""
50        def get(x):
51            a = []
52            while x != lca:
53                a.append(x)
54                x = self.par(x)
55            return a
56
57        lca = self.lca(u, v)
58        return get(u) + [lca] + get(v)[::-1]