전체 개미마을은 가장 깊은 곳에 여왕개미가 살고 있는 본부가 있고 그곳에 직접 연결된 여러개의 마을들로 구성되어 있다.

각 마을에는 또 다시 여러개의 작은 마을들이 연결되어 있다.

이러한 구조를 그래프로 표현하면 여왕개미가 살고 있는 본부를 루트로 하는 트리 모양이 된다.

여왕개미가 살고 있는 본부는 1번이고 1번에 직접 연결된 마을을 2번부터 차례대로 번호를 붙이고

다시 그 마을들에 연결된 마을들의 번호를 차례대로 붙여 준다고 한다.

따라서 1번 마을을 제외하고 어느 마을이든, 그 마을의 번호는 그 마을의 상위마을 번호보다 큰 번호가 된다.

여왕개미는 자신의 하위 각 마을 그룹의 모든 개미들의 합을 일정하게 유지시켜서 마을간 평화를 유지시키려고 한다.

각 마을 또한 하위 마을 그룹의 모든 개미들의 합을 일정하게 유지시켜야 한다.

개미들은 현재 자신이 거주하는 마을을 떠나서 다른 마을로 이주하게 되면 기존 마을에 있던 개미들로부터 왕따를 당해서 적응 할 수가 없다.

여왕개미는 고민 끝에 새로운 마을을 만들어서 최소한의 개미들을 새로운 마을로 이동시키서 독립시켜 살게 하고

남는 개미들은 처음에 구상했던 각 마을 그룹별 마리수를 똑같게 만들려고 한다.

예를 들어 아래와 같은 마을의 구조가 있다면

2번 2마리, 3번 1마리, 5번 2마리, 7번 1마리, 8번 3마리, 9번 2마리 이렇게 11마리를 새로운 마을로 이동시키면

아래 그림과 같이 2번마을 그룹 , 3번마을 그룹, 4번마을 그룹의 개미 수가 모두 7마리로 같아지고,

2번 마을의 하위 마을들도 모두 1마리로 동일하고, 4번 마을의 하위 마을도 모두 2마리로 동일하게 되었다.

마을의 구조가 주어질 때 이동해야 하는 최소의 개미수를 출력하는 프로그램을 작성하라.

개미마을 timer 1s memory 64MB

개미마을 1s 64MB