Submission #2745282

Source Code Expand

Copy
```import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
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 = a-1, b-1
if depth[a] > depth[b]:  # 深いほうが後ろ
a, b = b, a

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]

```

#### Submission Info

Submission Time 2018-06-26 15:40:59+0900 D - 閉路 kenseiQ PyPy3 (2.4.0) 100 1379 Byte AC 1616 ms 164016 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Case Name Status Exec Time Memory