Binary Mobile Width

Enrollment keeps shrinking, so a kindergarten decided to build an oversized binary mobile to attract new students. The mobile is made of wooden rods, beads, and the strings that connect them.

• The kindergarten sits in a 2D world. There is no Z axis, and gravity pulls along the -Y direction.
• Every rod hangs from exactly one string. The string that holds rod 1 is attached to the ceiling.
• Each end of a rod carries one string, and below that string hangs either another rod or a bead.
• Every bead has a weight. Rods and strings weigh nothing.
• A rod is a segment of zero thickness, and a bead is a point mass of zero size.
• In the finished mobile every rod lies parallel to the X axis, that is, horizontal.

The principal has to clear a spot for the finished mobile and does not know how far it spreads sideways. Given how the rods and beads are connected, the length of each rod, and the weight of each bead, compute the width of the finished mobile. The width is the largest X coordinate the mobile reaches minus the smallest.

The first line has the number of test cases $T$.

The first line of each test case has the number of rods $n$ ($1 \leq n \leq 100{,}000$). The $i$-th of the next $n$ lines has the length of rod $i$, $len$ ($1 \leq len \leq 1{,}000$), then two integers $l$ and $r$ describing what hangs from the left end and from the right end, separated by spaces.

If $-n \leq l \leq -1$, rod $-l$ hangs from the left end. If $1 \leq l \leq 100{,}000$, a bead of weight $l$ hangs from the left end. Read $r$ the same way, except that it describes the right end.

All rods belong to one connected structure rooted at rod 1, and each of rods 2 through $n$ hangs from exactly one rod end.

For each test case print the width of the mobile on its own line. Round to six digits after the decimal point and pad with zeros, so a width of exactly 5 prints as 5.000000.

A rod stays horizontal when the torque on both sides of its hanging point is equal. Write $W_l$ for the weight hanging on the left side of a rod of length $len$, and $W_r$ for the weight on the right side. The hanging point sits $\dfrac{len \times W_r}{W_l + W_r}$ from the left end and $\dfrac{len \times W_l}{W_l + W_r}$ from the right end.

The weight carried by a rod is the sum of the weights of every bead below it. Rods and strings weigh nothing, so they add nothing.