Submission #4653127

---

Source Code Expand

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

LCA = list(range(N+1))


def getV(lca,inte):#inteが経由する頂点を全て返す。ただしLCAは1を基準とする。
#全ての頂点が辺でつながれない、または閉路が存在する場合兵庫県警に逮捕される
            if inte == 1:
                return [1]
            elif lca[inte] == 1:
                return [1,inte]
            else:
                return getV(lca,lca[inte])+[inte]

def getD(lca,int1,int2):#int1 < int2 である方が望ましい
        
    L1 = getV(lca,int1)
    L2 = getV(lca,int2)
    length1 = -1
    length2 = 0
    for l in L1[::-1]:
        length1 += 1
        if L2.__contains__(l):
            length2 = len(L2[L2.index(l):])-1
            break
    return length1+length2
        
            
    
    
for x,y in XY:
    LCA[max(x,y)] = min(x,y) 

for a,b in AB:
    print(getD(LCA,min(a,b),max(a,b))+1)

Submission Info

Judge Result