[백준] 5820. 경주

https://www.acmicpc.net/problem/5820

접근법

• centroid decomposition
• 거리 배열을 갱신해나감
  • 거리를 만들기 위한 길이가 최소인 것을 유지
  • centroid를 지나는 경로 중 길이가 k인 경로를 찾기 위해
  • $k-x$의 길이 + $k$의 길이가 최소인지를 확인

후기

• centroid decomposition을 공부하다가 접근한 문제임
• 너무 못찾아서 IOI 2011 테스트케이스를 참고해서 겨우 찾음
• 배열의 갱신을 되게 잘 해줘야함
• 분할 후 centroid를 지나는 경로를 찾을 때 거리 배열 갱신 오류가 많았음
  • 한쪽으로 내려가면서 거리를 바로 갱신하면 안됨
    • $k=50이라고 할 때$, centroid에서 내려가는 순서대로 $(dist,depth)$일때 예를 들어
    • $(10, 1) (10, 2) (10, 3) (10, 4) (10, 5)$
    • 원하는 방향은 len = 5이지만, len=4로 구해짐 (중간에 거리 10에 대해서 길이가 1로 갱신이 되므로..)
  • 한쪽에서 올라오는 경우에 바로 갱신을 해도 안됨
    • centroid 저 아래쪽 어딘가에서 바로 갱신이 되는 경우가 생겨서
    • 중간 어딘가에서 갱신한 값을 이용할 수도 있음
• 최종은 centroid 기준으로 한쪽 서브트리가 완전히 끝난 후에 값을 갱신해줬음