Submission #7490059

---

Source Code Expand

def resolve():
    import math
    import sys
    sys.setrecursionlimit(2147483647)
    class DoublingLCA:
        """
        LCA ダブリング版
        初期化 O(NlogN)、クエリ O(logN)
        """

        def __init__(self,edges,root=0):
            """
            :param list of (list of int) edges:
            :param int root=0:
            """
            self.edges = edges
            self.n = len(edges)
            self.root = root

            self.MAX_LOG_V = self.n.bit_length()
            self.depths = [-1] * self.n
            self.parents = [[-1] * self.n for _ in range(self.MAX_LOG_V)]

            self.__dfs(-1,root,0)
            self.__doubling()

        def __dfs(self,par,cur,dep):
            self.depths[cur]=dep
            self.parents[0][cur]=par
            for v in self.edges[cur]:
                if v!=par:
                    self.__dfs(cur,v,dep+1)

        def __doubling(self):
            for k in range(self.MAX_LOG_V - 1):
                for v in range(self.n):
                    if self.parents[k][v] < 0: # 親がない
                        continue
                    self.parents[k+1][v]=self.parents[k][self.parents[k][v]]

        def get(self, u, v):
            # 深さを合わせる
            if self.depths[u] > self.depths[v]:
                u, v = v, u
            for k in range(self.MAX_LOG_V):
                if (self.depths[v] - self.depths[u]) >> k & 1:
                    v = self.parents[k][v]
            if v == u:
                return v

            # にぶたん
            for k in reversed(range(self.MAX_LOG_V)):
                if self.parents[k][u] != self.parents[k][v]:
                    u = self.parents[k][u]
                    v = self.parents[k][v]
            return self.parents[0][u]

        def distance(self, u, v):
            """
            u, v 間の距離
            depth[u] + depth[v] - depth[lca]*2
            :param u:
            :param v:
            :rtype: int
            """
            lca = self.get(u, v)
            return self.depths[u] + self.depths[v] - self.depths[lca] * 2


    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N - 1)]
    Q = int(input())
    AB = [list(map(int, input().split())) for _ in range(Q)]

    edges = [[] for _ in range(N + 1)]
    for x, y in XY:
        edges[x - 1].append(y - 1)
        edges[y - 1].append(x - 1)
    LCA = DoublingLCA(edges=edges)

    for a, b in AB:
        d = LCA.distance(a - 1, b - 1)
        print(d + 1)

resolve()

Submission Info

Judge Result