백준 17399 트리의 외심 - 정당성 증명

https://acmicpc.net/problem/17399

트리 위 노드 a,b,c의 외심을 찾는 문제.

외심은 정의는 다음과 같다.
1. 동일성 -> dist(a,b) = dist(b,c) = dist(c,a)
2. 최소성

a와 b의 가장 가까운 중점을 M이라 해보자.
M에서 a와 b쪽이 아닌 다른 방향 (부모 혹은 자식)으로 간 것들도
모두 a와 b의 중점이 될 것이다. 거리를 d라 하자.
dist(M,c) = d라면 정답은 그대로 M이된다. (다른 방향으로 옮기면 d가 증가한다.)
dist(M,c) != d라면 M을 적당히 옮겨서 c와의 거리를 맞춰야 한다.
적당히 옮겨서 외심 M이 존재한다고 가정하자. 놀랍게도 이때의 M은 (a와 c의 중점) 혹은 (b와 c의 중점) 중 하나다.

만약 M이 (a,b) 의 중점도 아니고 (b,c)의 중점도 아니고, (c,a)의 중점도 아닌 경우가 있다고 가정하자.
이때 어떤 방향으로 한칸 움직이든 M과 a,b,c와의 거리는 모두 같다. (모두 각 쌍의 중점에서 시작하는 가지 위에 있기 때문).
따라서 (b,c)의 중점 쪽으로 한칸 이동한 M'을 생각하자.
(1)M과 (b,c)와의 거리는 1 감소한다.
(2) M과 (a,b), (a,c)와의 거리는 1 증가하거나 감소한다.
(3) (2)에서, (1)에 의해 항상 1 감소해야 한다. 

따라서 M'과 (a,b,c)와의 거리는 모두 1 감소하였다. 

즉, M은 외심의 최소성에 모순이다.
결론적으로 외심은 최소 세 개의 중점 중 하나다.

여기서 더 확장하여 n개 노드의 외심은 nC2개의 중점 쌍 중 하나임을 보일 수 있다.