提出 #5581449

---

ソースコード 拡げる

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

U = 17
N = int(input())
edge = [[] for _ in range(N+1)]

for _ in range(N-1):
  x,y = map(int,input().split())
  edge[x].append(y)
  edge[y].append(x)
   
# 頂点xから根に向かって2**i進んだ到達点
# 行き過ぎている場合は0
go_back = [[0]*U for _ in range(N+1)]
depth = [0] * (N+1)

def set(x,d,p):
  depth[x] = d
  go_back[x][0] = p
  for i in range(1,U):
    go_back[x][i] = go_back[go_back[x][i-1]][i-1]
    if go_back[x][i] == 0:
      break
  for y in edge[x]:
    if y == p:
      continue
    set(y,d+1,x)

set(1,0,0)

def calc_dist_same_depth(x,y):
  if x == y:
    return 0
  j = 0
  while go_back[x][j] != go_back[y][j]:
    j += 1
  if j == 0:
    return 2
  rx = go_back[x][j-1]
  ry = go_back[y][j-1]
  return calc_dist_same_depth(rx,ry) + (1<<j)

def calc_dist(x,y):
  dx = depth[x]
  dy = depth[y]
  d = dy - dx
  if d < 0:
    d = -d
    x,y = y,x
  result = d
  j = 0
  while d:
    bit = 1<<j
    if d&bit:
      y = go_back[y][j]
      d ^= bit
    j += 1
  return calc_dist_same_depth(x,y) + result

Q = int(input())
for _ in range(Q):
  a,b = map(int,input().split())
  print(calc_dist(a,b)+1)

提出情報

ジャッジ結果