백준 24520 - Meet In The Middle

문제 링크 : https://www.acmicpc.net/problem/24520

 

문제

신촌 왕국에는 1번부터 N번까지 N개의 마을이 있고 N-1개의 도로가 서로 다른 두 마을을 연결하고 있다. 모든 마을은 도로를 통해 다른 마을로 갈 수 있고, 이때 마을 내에서의 이동 거리는 무시할 수 있다.

현재 신촌 왕국은 "대칭병"의 대유행으로 혼란을 겪고 있다. 대칭병은 어떤 것이든 대칭을 이루지 않으면 심신이 불편해져 일상생활을 할 수 없게 만드는 병이다. 대칭병의 여파는 엄청났는데 심지어 사람과 사람 간의 만남조차 어렵게 됐다. 신촌 왕국의 두 사람이 만나는 상황을 생각해보자. 약속 장소가 둘 중 한 사람의 마을에 더 가깝다면 아주 불편해진다. 따라서 두 사람이 사는 각 마을까지의 거리가 정확히 같은 곳을 약속 장소로 정해야 할 것이다. 즉, Meet in the middle. 가운데에서 만나야 한다!

신촌 왕국 도로 정보와 만나려는 두 사람의 마을이 주어졌을 때, 약속 장소로 적절한 위치를 구해보자.

입력

첫 번째 줄에 마을의 수 N, 약속의 수 K가 주어진다. (1 ≤ N, K ≤ 100000)

이어지는 줄부터 N-1개의 줄에 도로 정보를 나타내는 세 정수 u, v, w가 주어진다. u번 마을과 v번 마을 사이에 길이 w의 도로가 있다는 뜻이다. (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ w ≤ 10^9)

이어지는 줄부터 K개의 줄에 만나려는 두 사람의 마을 번호 u, v가 주어진다. (1 ≤ u, v ≤ N)

출력

 K개의 줄에 두 사람의 만날 수 있는 마을의 번호를 출력한다. 그러한 마을이 없다면 -1을 출력한다. 가능한 답이 여러 가지라면, 두 사람이 사는 각 마을까지 거리의 합이 짧은 것을 출력한다.

풀이 과정

https://readytojoin.tistory.com/entry/LCA-%EC%B5%9C%EC%86%8C-%EA%B3%B5%ED%86%B5-%EC%A1%B0%EC%83%81-%EC%B0%BE%EA%B8%B0?category=1193467

LCA - 최소 공통 조상 찾기

 

마을의 수와 약속의 수가 많으니 LCA에 희소 배열을 사용한다.

 

희소 배열에 경로 간 거리 합을 저장하고, u와 v 사이의 거리가 정확히 2로 나누어 떨어지는지를 확인한다.

정확히 2로 나누어 떨어진다면 정확히 2로 나누어 떨어진 곳이 u 부터 LCA 까지 경로 안 인지 v 부터 LCA 까지 경로 안 인지를 크기로 판별한다. 두 경로 중 큰 거리를 가진 곳 안에 정확히 2로 나누어 떨어지는 정점이 존재한다면 정답 노드이므로, 해당 경로에서 처음부터 다시 탐색하여 정답 노드가 있는지 확인한다. 

# 24520. Meet In The Middle ( PLATINUM 3 )
import sys
input = sys.stdin.readline
sys.setrecursionlimit(110000)

n, k = map(int, input().rstrip().split())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
  u, v, w = map(int, input().rstrip().split())
  graph[u].append([v, w])
  graph[v].append([u, w])

# 1. 해당 경로 사이 총 거리 구하기
# 2. 정확히 2로 나누어진다면 절반에서 u->LCA 안에 있는지 v->LCA 안에 있는지 판별
# 3. 정확히 2로 나눈 거리에 정점이 있는지 확인

visited = [0 for _ in range(n+1)]
depth = [0 for _ in range(n+1)]
parent = [[-1, 0] for _ in range(n+1)]

def dfs(now, p, dep, pre_cost):
  global graph
  global visited
  global depth
  global parent

  depth[now] = dep
  for next, cost in graph[now]:
    if visited[next] == 0:
      visited[next] = 1
      dfs(next, now, dep + 1, cost)
  parent[now] = [p, pre_cost]

for i in range(1, n+1):
  if visited[i] == 0:
    visited[i] = 1
    dfs(i, -1, 0, 0)

# Sparse Table [0] : node [1] : cost
table = [[[0, 0] for _ in range(n+1)] for _ in range(21)]

for i in range(1, n+1): table[0][i] = [parent[i][0], parent[i][1]]
for i in range(1, 21):
  for j in range(1, n+1): 
    table[i][j] = [table[i-1][table[i-1][j][0]][0], table[i-1][table[i-1][j][0]][1] + table[i-1][j][1]]
def meet_in_the_middle(a, b):
  if depth[a] < depth[b]:
    a, b = b, a

  a_cost = 0
  b_cost = 0

  original_a = int(a)
  original_b = int(b)

  for i in range(20, -1, -1):
    if depth[a] - depth[b] >= (1 << i):
      a, now_cost = table[i][a]
      a_cost += now_cost

  if a == b:
    # a_cost 만 쌓인 상태
    # a -> LCA 거리가 절반으로 나누어 지는지, 절반으로 나누어진다면 그 안에 절반 거리의 노드가 있는지
    if a_cost % 2 != 0: return -1
    else:
      goal = a_cost // 2
      a = original_a

      for i in range(20, -1, -1):
        if table[i][a][1] <= goal:
          goal -= table[i][a][1]
          a = table[i][a][0]

      if goal == 0: return a
      else: return -1
      
  else:
    for i in range(20, -1, -1):
      if table[i][a][0] != table[i][b][0]:
        a, now_cost_a = table[i][a]
        b, now_cost_b = table[i][b]

        a_cost += now_cost_a
        b_cost += now_cost_b

    a, now_cost_a = table[0][a]
    b, now_cost_b = table[0][b]

    a_cost += now_cost_a
    b_cost += now_cost_b
    #print('cost', a_cost, b_cost)
    if (a_cost + b_cost) % 2 != 0: return -1
    else:
      if a_cost == b_cost: return a
      else:
        goal = (a_cost + b_cost) // 2
        if a_cost > b_cost:
          a = original_a

          for i in range(20, -1, -1):
            if table[i][a][1] <= goal:
              goal -= table[i][a][1]
              a = table[i][a][0]

          if goal == 0: return a
          else: return -1
        else: # a_cost < b_cost
          b = original_b

          for i in range(20, -1, -1):
            if table[i][b][1] <= goal:
              goal -= table[i][b][1]
              b = table[i][b][0]

          if goal == 0: return b
          else: return -1

for _ in range(k):
  a, b = map(int, input().rstrip().split())
  if a == b: print(a)
  else: print(meet_in_the_middle(a, b))