import sys
input = sys.stdin.readline
from collections import *
def findparent(x,d):
for i in range(l+1):
if d&(1<<i):
x = sparse[i][x]
return x
def findcoparent(x,y,c):
if not c:
if parent[x]==parent[y]:
return parent[x]
return sparse[1][x]
if sparse[c][x]==sparse[c][y]:
return findcoparent(x,y,c-1)
return findcoparent(sparse[c][x],sparse[c][y],c-1)
def LCA(x,y):
dx,dy = depth[x],depth[y]
if dx>dy:
x = findparent(x,dx-dy)
elif dx<dy:
y = findparent(y,dy-dx)
if x==y:
return x
return findcoparent(x,y,l)
N = int(input())
graph = [[] for i in range(N+1)]
for _ in range(N-1):
a,b = map(int,input().split())
graph[a].append(b); graph[b].append(a)
dq = deque([(1,1)])
parent = [0]*(N+1); depth = [0]*(N+1)
while dq:
now,d = dq.popleft()
depth[now] = d
for next in graph[now]:
if not depth[next]:
parent[next] = now
dq.append((next,d+1))
l = len(bin(d))-3
sparse = [parent] + [[0]*(N+1) for i in range(l)]
for i in range(1,l+1):
for n in range(1,N+1):
sparse[i][n] = sparse[i-1][sparse[i-1][n]]
result = 0; now = 1
for _ in range(int(input())):
next = int(input())
result += depth[now]+depth[next]-depth[LCA(now,next)]*2
now = next
print(result)
간단한 LCA [백준 11438번] LCA 2 (Python3) (tistory.com) 응용문제
LCA 알고리즘을 알고 있다면 쉽게 해결할 수 있다.
풀이를 설명하면,
1. 현재 노드와 방문해야하는 노드 now와 next에 대해서 LCA(now,next)를 구한다.
2. result에 (now의 깊이-LCA의 깊이) + (next의 깊이 - LCA의 깊이)를 더한다.
3. 결과를 출력한다.
아주 간단한 문제이지만 지문의 번역이 모호하게 되어있어서 시간을 좀 날린 문제였다. 방문해야하는 순서를 고려하지 않고 모든 도시를 방문하는 최솟값을 구하는 문제라고 생각해서 MST 응용문제라고 생각했는데, 그냥 LCA하면 되는 문제였다. 원문에는 정확하게 순서대로 방문하라는 말이 적혀있다고 하는데, 이 문제에는 그렇지 않아 시간을 좀 낭비했다. (참고 https://www.acmicpc.net/board/view/107549)
오늘의 교훈) 문제를 정확하게 이해하자