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 Ai–Ak.
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
(1 ≤ Ki < i ≤ N,
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.
Problem Author: Alexander Ipatov
Problem Source: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006