DMOPC '22 Contest 1 P5 - Wesley's Cabins

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Wesley recently bought a resort comprised of N cabins, numbered from 1 to N. He needs to distribute water to his N cabins, with different requirements R_i per cabin. Wesley doesn't care if any cabin gets more than the required amount of water, as long as they get at least R_i units.

At each cabin there is a lever, each of which produce a different output rate X_i, meaning that X_i units of water flow into cabin i if the lever is held for one second.

The cabins are connected by a network of N - 1 pipes. Wesley resides in cabin 1, the head cabin, and due to some interesting properties of the land around him, water always flows away from the head cabin.

Each pipe has a flow rate F_i. When Y units of water flows into a node, each connected pipe that leads away from the head cabin transfers F_i \times Y units of water into the adjacent cabin. Any water not moved into adjacent cabins is kept in the current cabin and contributes to the required amount of water.

Wesley can push each lever for any real number of seconds, but for some reason, he hates pressing levers. He wants to know how many total seconds he will have to press levers in order to fulfill the requirements for each cabin, and has enslaved politely asked you to help him.


1 \le N \le 10^5

0.001 \le R_i, X_i \le 10^9

0.001 \le F_i \le 0.9

R_i, X_i, and F_i are given with at most 3 decimal digits.

For any given cabin, the flow rates of adjacent pipes that lead away from cabin 1 will have a sum that is less than 1.

Subtask 1 [20%]

1 \le N \le 10

Subtask 2 [50%]

1 \le N \le 2 \times 10^3

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line will contain N, the number of cabins.

The next N lines will each contain two real numbers, R_i and X_i.

The next N - 1 lines will contain a_i, b_i and F_i, indicating that there is a connection between cabins a_i and b_i with flow rate F_i.

Output Specification

Output the number of seconds required for Wesley to be able to meet the requirements for each cabin. Your answer will be considered correct if it has an absolute or relative error of less than 10^{-6}.

Sample Input

1 1
2.5 10
2.5 5
5.5 5
1 2 0.25
1 3 0.25
1 4 0.4

Sample Output


Explanation for Sample

The graph is shown below.

If we press the lever at cabin 1 for 10 seconds, and the lever at cabin 4 for 0.3 seconds, all cabins will have at least the required amount of water. It can be proven that 10.3 is minimal.


There are no comments at the moment.