Submission #7489157

---

Source Code Expand

class LCA(object):
    def __init__(self,edges,root=0):
        self.edges=edges
        self.n=len(edges) # n=|V|
        # self.logn=(self.n-1).bit_length() # logn = ceil(log2(n))
        self.logn=18 # logn = ceil(log2(n))
        # initialization
        self.depth=[0]*self.n
        self.parent=[[-1]*(self.logn+1) for _ in range(self.n)] # parent[u][i]=v : uの2^i世代上がv(なければ-1)
        # construct
        self.__dfs(-1,root)
        self.__doubling()

    def __dfs(self,par,cur,dep=0):
        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.logn):
            for v in range(self.n):
                if self.parent[v][i]!=-1: # 半分遡った時点で親が存在しなければ-1のままにしておく。-1が返るとlistの末尾の値の取得になってしまう
                    self.parent[v][i+1]=self.parent[self.parent[v][i]][i]

    def get(self,u,v): # uとvとのLCAを返す
        dd=self.depth[v]-self.depth[u]
        if dd<0: # vの方が深いようにする
            u,v=v,u
            dd=-dd

        for i in range(self.logn): # dd分だけvを遡らせる
            if dd&(1<<i): # 各bitで判定
                v=self.parent[v][i]

        if u==v: return u # 高さ揃えた時点で一致してたら終わり

        for i in reversed(range(self.logn-1)): # そうでなければ上から二分探索
            pu,pv=self.parent[u][i],self.parent[v][i]
            if pu!=pv: u,v=pu,pv # 高さが一致してるので、片方だけ-1ということはない
        return self.parent[u][0]

#%%
# given data
N=int(input())
E=[[] for _ in range(N)]
root=0
for _ in range(N-1):
    u,v=map(lambda x:int(x)-1,input().split())
    E[u].append(v)
    E[v].append(u)
lca=LCA(E)
Q=int(input())
for _ in range(Q):
    u,v=map(lambda x:int(x)-1,input().split())
    print(lca.depth[u]+lca.depth[v]-2*lca.depth[lca.get(u,v)]+1)

Submission Info

Judge Result