Submission #2520708

---

Source Code Expand

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    G[x].append(y)
    G[y].append(x)

parent = [[] for i in range(N)]  # 親を2^k回辿って到達する頂点
depth = [None] * N
stack = []


def walk(i):
    rec_size = len(stack)
    depth[i] = rec_size

    # 親を2^k回辿る
    k = 0
    while 2**k <= rec_size:
        parent[i].append(stack[rec_size-2**k])
        k += 1

    stack.append(i)

    for ni in G[i]:
        if depth[ni] is not None:
            continue
        walk(ni)
    del stack[-1]


walk(0)

Q = int(input())
for i in range(Q):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if depth[a] > depth[b]:  # 深いほうが後ろ
        a, b = b, a

    depth_add = depth[a] + depth[b]
    depth_diff = depth[b] - depth[a]

    while depth_diff > 0:

        k = 1
        while 2**k < depth_diff:
            k += 1
        k -= 1

        b = parent[b][k]
        depth_diff -= 2**k

    while a != b:
        k = 1
        le = len(parent[a])

        while le > k and parent[a][k] != parent[b][k]:
            k += 1
        k -= 1
        a = parent[a][k]
        b = parent[b][k]

    print(depth_add - 2*depth[a] + 1)

Submission Info

Judge Result