https://www.acmicpc.net/problem/11438
시간 1.5초, 메모리 256MB
input :
- N(2 ≤ N ≤ 100,000)
- N-1개 줄 : 트리 상에서 연결된 두 정점
- M(1 ≤ M ≤ 100,000)
- M개 줄에는 정점 쌍
output :
- 첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력
조건 :
-
트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.
-
두 노드의 가장 가까운 공통 조상이 몇 번인지 출력
앞의 LCA를 개선해야만 해결이 가능한 문제이다.
개선
우선 개선된 방향을 본다면 lca함수 내에서 이동을 log의 방식으로 움직인다.
그렇기에 시간 복잡도는 매우 강력해지지만 2^0 ~ 2^x까지의 노드를 기록하고 있어야 한다.
고로 메모리와 시간 복잡도를 교환했다고 볼 수 있지만 일단 시간은 빨라진다....
DP
이 LCA에서는 모든 노드를 기록하고 있어야 한다고 했다.
우리가 LCA를 구현할 때 parent에 정의한 것은 2^0 위 칸에 존재하는 노드의 정보이다.
고로 이를 2차원 배열을 통해 모두 저장하고 있게 할 수 있다.
dfs를 수행한 다음에 2^1 ~ 2^x까지 돌면서 점진적으로 저장핟도록 해야 한다.
왜냐? 맨 처음에 가지고 있는 정보는 2^0에 위치한 놈 밖에 없기 때문에 그러하다.
# 2^i 번째의 부모 노드의 값을 저장.
for i in range(1, 21):
# j번째 노드 기준으로.
for j in range(1, n + 1):
# 2번쨰 칸 위의 값을 저장하려 할 때
# 현재 노드의 부모 노드로 이동 부모 노드의 "부모"노드의 값을 가져옴.
# 이러한 단계로 모든 DP를 초기화 함.
parent[j][i] = parent[parent[j][i - 1]][i - 1]parent[j][i - 1] 얘를 통해서 2^(i - 1) 위 칸에 위치하는 놈의 2^(i - 1) 위에 존재하는 노드를 가져올 수 있다. 암튼 타고 타고 올라가서 가져오는 것이다.
lca
lca 파트에서는 이동 가능한 모든 위치를 확인 하는 것이다.
현재 존재하는 깊이의 차이가 9인 경우에는
8칸 위, 1칸 위 이렇게 움직이는 것이다.
저렇게 이동할 수 있는 위치일 때 그 위치에 존재하는 부모를 찾는 것이 이 문제를 관통하는 원칙이다.
import sys
sys.setrecursionlimit(100000)
def dfs(node, depth):
visit[node] = True
d[node] = depth
for next_node in graph[node]:
if visit[next_node] == 1:
continue
parent[next_node][0] = node
dfs(next_node, depth + 1)
def set_parent():
"""
dp로 모든 부모 관계를 저장한다.
"""
dfs(1, 0)
# 2^i 번째의 부모 노드의 값을 저장.
for i in range(1, 21):
# j번째 노드 기준으로.
for j in range(1, n + 1):
# 2번쨰 칸 위의 값을 저장하려 할 때
# 현재 노드의 부모 노드로 이동 부모 노드의 "부모"노드의 값을 가져옴.
# 이러한 단계로 모든 DP를 초기화 함.
parent[j][i] = parent[parent[j][i - 1]][i - 1]
def lca(high, low):
# 가지고 있는 값이 클수록 더 깊이 있는 거임.
if d[high] > d[low]:
high, low = low, high
# 2^20 ~ 2^0 까지 반복을 수행
for log in range(20, -1, -1):
if d[low] - d[high] >= (1 << log):
low = parent[low][log]
# 서로 동일한 노드 인 경우.
if high == low:
return high
for log in range(20, -1, -1):
if parent[high][log] != parent[low][log]:
low = parent[low][log]
high = parent[high][log]
return parent[high][0]
n = int(sys.stdin.readline())
graph = [[] for _ in range(n + 1)]
parent = [[0] * 21 for _ in range(n + 1)]
d = [0] * (n + 1)
visit = [0] * (n + 1)
for i in range(n - 1):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
set_parent()
m = int(sys.stdin.readline())
for i in range(m):
a, b = map(int, sys.stdin.readline().split())
print(lca(a, b))
