def init_tree(self, root=0):
    self.depth = {root: 0}
    self.dist = {root: 0}
    self.ancestors = [{root: root}]
    stack = [root]
    while stack:
        u = stack.pop()
        for (v, e) in self.edges[u].items():
            if (v == self.ancestors[0][u]):
                continue
            self.dist[v] = (self.dist[u] + e['weight'])
            self.depth[v] = (self.depth[u] + 1)
            self.ancestors[0][v] = u
            stack.append(v)
    for _ in range(max(self.depth).bit_length()):
        ancestor = self.ancestors[(- 1)]
        nxt_ancestor = {v: ancestor[ancestor[v]] for v in self.nodes}
        self.ancestors.append(nxt_ancestor)
def init_tree(self, root=0):
    self.depth = {root: 0}
    self.dist = {root: 0}
    self.ancestors = [{root: root}]
    stack = [root]
    while stack:
        u = stack.pop()
        for (v, e) in self.edges[u].items():
            if (v == self.ancestors[0][u]):
                continue
            self.dist[v] = (self.dist[u] + e['weight'])
            self.depth[v] = (self.depth[u] + 1)
            self.ancestors[0][v] = u
            stack.append(v)
    for _ in range(max(self.depth).bit_length()):
        ancestor = self.ancestors[(- 1)]
        nxt_ancestor = {v: ancestor[ancestor[v]] for v in self.nodes}
        self.ancestors.append(nxt_ancestor)