Submission #1708246

---

Source Code Expand

import math
 
N = int(input())
 
C = [[] for _ in range(N)]
for _ in range(N - 1):
    x, y = [int(_) - 1 for _ in input().split()]
    C[x].append(y)
    C[y].append(x)
 
log_N = int(math.log2(N)) + 1
 
dbl = [[-1] * log_N for _ in range(N)]
dep = [0] * N
 
# initialize
queue = [(0, -1, 0)]  # (node, parent, depth), root: 0
while len(queue) > 0:
    node, parent, depth = queue.pop()
    dep[node] = depth
    for edge in C[node]:
        if edge == parent:
            continue
        dbl[edge][0] = node
        queue.append((edge, node, depth + 1))
 
# doubling
for j in range(1, log_N):
    for i in range(N):
        if dbl[i][j-1] == -1:
            continue
        dbl[i][j] = dbl[dbl[i][j-1]][j-1]
 
    j += 1
 
def LCA(a, b):
 
    def func(leaf, d):
        res = leaf
        for i in range(log_N):
            if (d >> i) & 1:
               res = dbl[res][i]
            i += 1
 
        return res
 
    if dep[a] > dep[b]:
        a, b = b, a
    _a, _b = a, func(b, dep[b] - dep[a])
 
    if _a == _b:
        return _a
    else:
        for i in range(log_N - 1, -1, -1):
            if dbl[_a][i] != dbl[_b][i]:
                _a = dbl[_a][i]
                _b = dbl[_b][i]
 
        return dbl[_a][0]
 
# main
Q = int(input())
for _ in range(Q):
    a, b = [int(_) - 1 for _ in input().split()]
    print(dep[a] + dep[b] - 2 * dep[LCA(a, b)] + 1)

Submission Info

Judge Result