문제
전체 개미마을은 가장 깊은 곳에 여왕개미가 살고 있는 본부가 있고 그곳에 직접 연결된 여러개의 마을들로 구성되어 있다.
각 마을에는 또 다시 여러개의 작은 마을들이 연결되어 있다.
이러한 구조를 그래프로 표현하면 여왕개미가 살고 있는 본부를 루트로 하는 트리 모양이 된다.
여왕개미가 살고 있는 본부는 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마리로 동일하게 되었다.
마을의 구조가 주어질 때 이동해야 하는 최소의 개미수를 출력하는 프로그램을 작성하라.
입력
입력의 첫줄에는 마을의 수 N이 입력된다. (1 ≤ N ≤ 100)
다음줄부터 N개의 줄에는 각 마을의 정보가 각각 3개의 정수로 주어지는데 첫 번째는 마을의 번호,
두 번째는 연결된 상위 마을번호, 세 번째는 현재 마을의 개미숫자를 의미한다.
마을번호는 1~N 사이의 정수이고 마을별 개미 숫자는 100마리 이하이다.
출력
이동해야 하는 최소의 개미수를 출력한다.
예제
9
1 0 2
2 1 7
3 1 8
4 1 1
5 2 3
6 2 1
7 4 3
8 4 5
9 4 4
11
로그인해야 코드를 작성할 수 있어요.