트리 위의 모임

위의 그림과 같은 트리 위의 세 사람이 세 정점 , , 위에 한 명씩 서 있다. 이 세 사람이 한 정점에서 모이려면, 정점 를 택해서, 각자 정점 로 최단 거리로 이동해야 한다. 이 때 이동해야 하는 최단 거리의 합을 라고 하자.

즉, 가 정점 와 정점 사이의 최단 거리라면, 이다.

모든 쌍에 대해, 의 값을 모두 합치면 얼마인가?

문제 형식

주관식

출처

• KOI 2023 1차대회 고등부 1교시 8번
• KOI 2023 1차대회 중등부 1교시 11번