forked from ndb796/python-for-coding-test
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path6.py
More file actions
60 lines (52 loc) ยท 1.83 KB
/
6.py
File metadata and controls
60 lines (52 loc) ยท 1.83 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import sys
input = sys.stdin.readline # ์๊ฐ ์ด๊ณผ๋ฅผ ํผํ๊ธฐ ์ํ ๋น ๋ฅธ ์
๋ ฅ ํจ์
sys.setrecursionlimit(int(1e5)) # ๋ฐํ์ ์ค๋ฅ๋ฅผ ํผํ๊ธฐ ์ํ ์ฌ๊ท ๊น์ด ์ ํ ์ค์
LOG = 21 # 2^20 = 1,000,000
n = int(input())
parent = [[0] * LOG for _ in range(n + 1)] # ๋ถ๋ชจ ๋
ธ๋ ์ ๋ณด
d = [0] * (n + 1) # ๊ฐ ๋
ธ๋๊น์ง์ ๊น์ด
c = [0] * (n + 1) # ๊ฐ ๋
ธ๋์ ๊น์ด๊ฐ ๊ณ์ฐ๋์๋์ง ์ฌ๋ถ
graph = [[] for _ in range(n + 1)] # ๊ทธ๋ํ(graph) ์ ๋ณด
for _ in range(n - 1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
# ๋ฃจํธ ๋
ธ๋๋ถํฐ ์์ํ์ฌ ๊น์ด(depth)๋ฅผ ๊ตฌํ๋ ํจ์
def dfs(x, depth):
c[x] = True
d[x] = depth
for y in graph[x]:
if c[y]: # ์ด๋ฏธ ๊น์ด๋ฅผ ๊ตฌํ๋ค๋ฉด ๋๊ธฐ๊ธฐ
continue
parent[y][0] = x
dfs(y, depth + 1)
# ์ ์ฒด ๋ถ๋ชจ ๊ด๊ณ๋ฅผ ์ค์ ํ๋ ํจ์
def set_parent():
dfs(1, 0) # ๋ฃจํธ ๋
ธ๋๋ 1๋ฒ ๋
ธ๋
for i in range(1, LOG):
for j in range(1, n + 1):
parent[j][i] = parent[parent[j][i - 1]][i - 1]
# A์ B์ ์ต์ ๊ณตํต ์กฐ์์ ์ฐพ๋ ํจ์
def lca(a, b):
# b๊ฐ ๋ ๊น๋๋ก ์ค์
if d[a] > d[b]:
a, b = b, a
# ๋จผ์ ๊น์ด(depth)๊ฐ ๋์ผํ๋๋ก
for i in range(LOG - 1, -1, -1):
if d[b] - d[a] >= (1 << i):
b = parent[b][i]
# ๋ถ๋ชจ๊ฐ ๊ฐ์์ง๋๋ก
if a == b:
return a;
for i in range(LOG - 1, -1, -1):
# ์กฐ์์ ํฅํด ๊ฑฐ์ฌ๋ฌ ์ฌ๋ผ๊ฐ๊ธฐ
if parent[a][i] != parent[b][i]:
a = parent[a][i]
b = parent[b][i]
# ์ดํ์ ๋ถ๋ชจ๊ฐ ์ฐพ๊ณ ์ ํ๋ ์กฐ์
return parent[a][0]
set_parent()
m = int(input())
for i in range(m):
a, b = map(int, input().split())
print(lca(a, b))