여러 개의 농장을 운영하는 농부 경원이는 가뭄으로 물이 부족해지자 자신의 농장들에 물을 공급할 계획을 세웠다. 가뭄을 대비하여 아주 큰 저수지를 관리해왔으며 저수지에는 물이 충분히 있다고 한다.

문제는 저수지로부터 떨어져 있는 각 농장들에 물을 어떻게 공급할 것인가? 하는 것이다. 각 농장들은 저수지와의 거리도 제각각이고 고도(일부 농장은 저수지보다 고도가 높을 수 있다고 한다.) 또한 서로 달라서 수로나 배관만 설치하는 것으로는 물을 공급할 수 없다고 한다. 따라서 농장과 저수지 사이에 여러 개의 중계지와 배관을 건설하고 중계지와 중계지 사이 또는 중계지와 농장 사이 배관에 펌프를 설치하여 다음 중계지 또는 농장에 물을 공급하기로 하였다.

아래 예를 보자. 저수지로부터 1번 중계지에 12L의 물이 보내졌다. 1번 중계지에서 2번 중계지로 12L의 30%가, 3번 중계지로 12L의 70%가 보내졌다. 따라서 2번 중계지에는 3.6L가 있을 것이고 3번 중계지에는 8.4L가 있을 것이다. 4번과 5번은 농장이고 각각 3.6L, 8.4L의 물을 공급받게 된다.

그런데 몇몇 중계지와 중계지 사이의 펌프는 매직펌프라고 한다. 매직 펌프는 현재 보낼 수 있는 물의 양을 제곱한 만큼 보낼 수 있다고 한다. 위 그림에서 2번 중계지와 4번 농장사이의 배관에 설치된 펌프가 매직 펌프라고 한다면 최대 3.6 * 3.6 = 12.96L 까지 보낼 수 있게 된다.. 매직 펌프에는 스위치가 달려있어 경원이가 원할 경우에는 그 기능을 켜거나 끌수 있다.

위 그림을 트리로 볼 때 각 중계지와 농장을 노드로 볼 수 있으며 단말노드가 농장이 된다. 물을 보내는 것은 그만큼의 비용이 들며 사업가인 경원이는 가능한 비용을 적게 쓰고자 한다. 노드와 노드 사이에 대한 정보와 농장노드에 대한 정보를 입력받아 경원이가 사용해야 하는 물의 최소양을 구하는 프로그램을 작성하시오.

#2905 upload 32 done 20 how_to_reg 12 auto_awesome スペシャルジャッジ

매직펌프 timer 1s memory 128MB

#2905
スペシャルジャッジ

매직펌프 1s 128MB