Submission #7490850

---

Source Code Expand

import sys
sys.setrecursionlimit(10**8)
def resolve():
    import math
    class DoublingLCA:
        """
        construct: O(NlogN)
        query 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.logn = (self.n-1).bit_length()
            self.depths = [-1] * self.n
            self.parents = [[-1] * self.n for _ in range(self.logn)]

            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.logn - 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):
            # 深さを合わせる
            dd=self.depths[v]-self.depths[u]
            if dd<0:
                u, v = v, u
                dd*=-1
            for k in range(self.logn):
                if dd&(1<<k):
                    v = self.parents[k][v]
            if v == u:
                return v

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


    # input
    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)]
    for x, y in XY:
        edges[x - 1].append(y - 1)
        edges[y - 1].append(x - 1)
    lca = DoublingLCA(edges)
 
    for u,v in AB:
        u=u-1
        v=v-1
        print(lca.depths[u]+lca.depths[v]-2*lca.depths[lca.get(u,v)]+1)

resolve()

Submission Info

Judge Result