Skip to content

Commit 4324395

Browse files
ndb796ndb796
authored
Update 6.py
1 parent d6b235f commit 4324395

File tree

1 file changed

+60
-0
lines changed

1 file changed

+60
-0
lines changed

‎21/6.py‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
import sys
2+
input = sys.stdin.readline # 시간 초과를 피하기 위한 빠른 입력 함수
3+
sys.setrecursionlimit(int(1e5)) # 런타임 오류를 피하기 위한 재귀 깊이 제한 설정
4+
LOG = 21 # 2^20 = 1,000,000
5+
6+
n = int(input())
7+
parent = [[0] * LOG for _ in range(n + 1)] # 부모 노드 정보
8+
d = [0] * (n + 1) # 각 노드까지의 깊이
9+
c = [0] * (n + 1) # 각 노드의 깊이가 계산되었는지 여부
10+
graph = [[] for _ in range(n + 1)] # 그래프(graph) 정보
11+
12+
for _ in range(n - 1):
13+
a, b = map(int, input().split())
14+
graph[a].append(b)
15+
graph[b].append(a)
16+
17+
# 루트 노드부터 시작하여 깊이(depth)를 구하는 함수
18+
def dfs(x, depth):
19+
c[x] = True
20+
d[x] = depth
21+
for y in graph[x]:
22+
if c[y]: # 이미 깊이를 구했다면 넘기기
23+
continue
24+
parent[y][0] = x
25+
dfs(y, depth + 1)
26+
27+
# 전체 부모 관계를 설정하는 함수
28+
def set_parent():
29+
dfs(1, 0) # 루트 노드는 1번 노드
30+
for i in range(1, LOG):
31+
for j in range(1, n + 1):
32+
parent[j][i] = parent[parent[j][i - 1]][i - 1]
33+
34+
# A와 B의 최소 공통 조상을 찾는 함수
35+
def lca(a, b):
36+
# b가 더 깊도록 설정
37+
if d[a] > d[b]:
38+
a, b = b, a
39+
# 먼저 깊이(depth)가 동일하도록
40+
for i in range(LOG - 1, -1, -1):
41+
if d[b] - d[a] >= (1 << i):
42+
b = parent[b][i]
43+
# 부모가 같아지도록
44+
if a == b:
45+
return a;
46+
for i in range(LOG - 1, -1, -1):
47+
# 조상을 향해 거슬러 올라가기
48+
if parent[a][i] != parent[b][i]:
49+
a = parent[a][i]
50+
b = parent[b][i]
51+
# 이후에 부모가 찾고자 하는 조상
52+
return parent[a][0]
53+
54+
set_parent()
55+
56+
m = int(input())
57+
58+
for i in range(m):
59+
a, b = map(int, input().split())
60+
print(lca(a, b))

0 commit comments

Comments
 (0)