ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1472. Martian Army

Time limit: 1.0 second
Memory limit: 64 MB
Many centuries ago Martians switched to using huge robots for military operations. During the current Moon conquest campaign, all of the Martian army is located at the headquarters on Mars, and each person is controlling the actions of his robot. There is a strict hierarchy in the Martian army: each person excepting the general (there is only one general in the army) has a direct commander. According to the army regulations, communication is allowed only between a commander and his direct subordinate. The communication is carried out via the headquarters local network. At the headquarters, each military person has his own computer, and computers are numbered from 1 to N, where N is the size of the Martian army. It is a tradition that a subordinate's computer has number that is greater than the number of his commander's computer. Each military person, in addition to the number of his computer, is characterized by his reliability. This is a real number; the owner of the computer i has reliability Ai. The general has reliability 1, and soldiers (soldiers and only they have no subordinates) have reliability 0.
The traffic in the headquarters network is not free for the military. For every megabyte of traffic between the ith computer and the computer of the commander of the ith computer's owner, the central Martian provider demands Ci Martian dollars in payment. The complication is that the volume of traffic between any two headquarters computers is a state secret, and is unknown even to the provider. Every month the provider sends a bill, and the military write there the traffic (a whole number of megabytes) themselves. Let a commander and his subordinate have computers with numbers i and k respectively. According to the contract with the provider, the traffic between the computers i and k must be not less than AiAk. In the beginning of every month, the provider's representatives know the hierarchy in the Martian army and costs of a megabyte of traffic, but they don't know the numbers Ai except for the general and soldiers, and of course they don't know beforehand the amounts of traffic that the military will write in the bill. It is interesting to know the guaranteed amount of money that the provider will receive from the military.


The first line contains the size of the army 2 ≤ N ≤ 100000. Each of the next N–1 lines contains integers Ki and Ci, which are the number of the computer of the commander of the ith computer's owner and the cost of a megabyte of traffic between the computers i and Ki (1 ≤ Ki < iN, 0 ≤ Ci ≤ 1000).


Output the minimal guaranteed amount of payment to the provider in Martian dollars. This amount must be a real number given with exactly two decimal digits.


1 10
2 5
2 3
3 1
3 2
3 3
Problem Author: Alexander Ipatov
Problem Source: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006