Ant Feeding through Super Pipes

Bobi feeds his favorite pet ants using a liquid that flows through a tree‐structured pipeline system. The system is represented by a tree with \( n \) nodes where node \( 1 \) is the root. Each edge from a parent to its child has an associated liquid flow percentage \( \frac{x}{100} \). For a normal pipe, the child simply receives \( L \times \frac{x}{100} \) liquid if the parent has \( L \) liquid. However, some pipes are super pipes that Bobi can enable or disable. If a super pipe is enabled and the liquid flow from the parent is \( L \), then the child receives \( (L \times \frac{x}{100})^2 \). (If the super pipe is disabled, it works like a normal pipe.)

It is guaranteed that for every node the sum of the outgoing percentages is \( 100 \). Each leaf of the tree represents the home of the ants, and a required amount of liquid is specified for each leaf to feed the ants properly.

Your task is to determine the minimum amount of liquid that Bobi must purchase at the root such that, by choosing optimally which super pipes to enable (using the rule below), every leaf receives at least its required amount.

Note on Super Pipe Decision: At any super pipe, if the liquid reaching the pipe multiplied by \( \frac{x}{100} \) is at least \( 1 \), then enabling the super pipe (and thus squaring the flow) will always yield a higher amount for that branch. Otherwise, it is optimal to leave it disabled.

Mathematically: For an edge with flow percentage \( \frac{x}{100} \) and parent liquid \( L \):

• If the pipe is normal or the super pipe is disabled, the child gets \( L \times \frac{x}{100} \).
• If it is a super pipe and is enabled (which you should do if \( L \times \frac{x}{100} \ge 1 \)), then the child gets \( (L \times \frac{x}{100})^2 \).

The decisions at super pipes are global: the same setting applies to the entire system and affects all leaves that use that pipe. Since increasing the root liquid increases the liquid at every leaf monotonically, you can use a binary search combined with a DFS simulation of the liquid flow through the tree to determine the minimum required root liquid.

inputFormat

The first line contains an integer \( n \) (number of nodes in the tree, \( 2 \le n \le 10^5 \)).

Then follow \( n-1 \) lines, each containing four space-separated values:

• \( u \): the parent node index,
• \( v \): the child node index,
• \( x \): an integer representing the flow percentage (the actual fraction is \( \frac{x}{100} \)),
• \( s \): a flag (either 0 or 1) indicating whether the pipe is a super pipe (1) or a normal pipe (0).

The next line contains an integer \( m \): the number of leaves (which will match the actual leaf count in the tree).

Then follow \( m \) lines. Each of these lines contains an integer and a floating‐point number: the leaf node id and the required amount of liquid for that leaf.

outputFormat

Output a single floating-point number: the minimum amount of liquid Bobi must purchase at the root. Answers with an absolute or relative error of at most \( 10^{-6} \) will be accepted.

sample

3
1 2 30 1
1 3 70 0
2
2 12.96
3 8.4

12.000000