Submission #7489134

---

Source Code Expand

def resolve():
    class LCA:
        def __init__(self,edges,root=0):
            self.edges=edges
            self.n=len(edges)
            self.maxLog=18
            self.parent=[[-1]*(self.maxLog+1) for _ in range(self.n)]
            self.depth=[0]*self.n
            self.__dfs(-1,root,0)
            self.__doubling()

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

        def __doubling(self):
            for i in range(self.maxLog):
                for v in range(self.n):
                    if self.parent[v][i]!=-1:
                        self.parent[v][i+1]=self.parent[self.parent[v][i]][i]

        def get(self,a,b):
            if self.depth[a]>self.depth[b]:
                a,b=b,a
            for i in range(self.maxLog):
                if (self.depth[b]-self.depth[a])&(1<<i):
                    b=self.parent[b][i]
            if a==b:
                return b
            for i in reversed(range(self.maxLog-1)):
                if self.parent[a][i]!=self.parent[b][i]:
                    a=self.parent[a][i]
                    b=self.parent[b][i]
            return self.parent[a][0]

    n=int(input())
    edges=[[] for _ in range(n)]
    for _ in range(n-1):
        x,y=map(lambda i: int(i)-1,input().split())
        edges[x].append(y)
        edges[y].append(x)
    lca=LCA(edges)
    q=int(input())
    for i in range(q):
        a,b=map(lambda x: int(x)-1,input().split())
        print(lca.depth[a]+lca.depth[b]-lca.depth[lca.get(a,b)]+1)
resolve()

Submission Info

Judge Result