백준5820 경주

문제 링크

  • http://icpc.me/5820

문제 출처

  • 2011 IOI 2번 (Day1 2번)

사용 알고리즘

  • Centroid Decomposition

풀이

트리에서 분할정복을 합시다!

트리에서 센트로이드를 제거해주면, 여러 개의 트리로 나눠지게 됩니다.
센트로이드에 의해 분할된 트리 안에서 만들어지는 경로들은 해당 트리에 대한 함수 호출(분할)에서 잘 처리할 것이기 때문에, 센트로이드를 지나는 경로에 대해서만 처리(정복)를 해주면 됩니다.