어긋나는 정점

정점 15개의 이진 트리가 있고, 정점마다 수가 적혀 있어요. 이웃한 두 정점 x(자식)와 y(부모)가 다음 중 하나를 만족하면 ‘어긋난다’고 해요. ① x 가 y 의 왼쪽 자식인데 x 의 수가 y 의 수보다 크다. ② x 가 y 의 오른쪽 자식인데 x 의 수가 y 의 수보다 작다. 맨 아래 잎이 아닌 정점을 누르면 그 정점의 왼쪽 서브트리와 오른쪽 서브트리가 서로 바뀌어요. 어긋나는 쌍의 수를 가장 적게 만드세요.

출처: 한국정보올림피아드(KOI) 2024 1차 대회 중등부 · 어긋나는 정점 (https://www.biko.kr/problem/2272) · 비코(biko.kr, 사단법인 한국비버정보교육연합)에서 발췌했으며 허락을 받아 다시 구현해 사용했습니다.