이진 모빌의 가로 폭

학생 수가 줄어드는 가운데 신입생을 끌어모으려고 한 유치원이 특대형 이진 모빌 만들기에 나섰다. 모빌은 나무 막대, 구슬, 그리고 이 둘을 잇는 실로만 이루어진다.

• 유치원은 2D 나라에 있다. Z축이 없고 중력은 -Y축 방향으로 작용한다.
• 막대는 저마다 실 하나에 매달려 있다. 1번 막대를 매단 실은 천장에 붙어 있다.
• 막대의 양 끝에는 실이 하나씩 달려 있고, 그 실의 아래쪽에는 다른 막대나 구슬이 매달려 있다.
• 구슬마다 무게가 정해져 있고, 막대와 실의 무게는 0이다.
• 막대는 두께가 0인 선분이고, 구슬은 크기가 0인 질량점이다.
• 모빌이 완성되면 모든 막대는 X축과 평행하게, 즉 수평으로 놓인다.

원장 선생님은 완성한 모빌을 걸 자리를 마련해야 하는데 모빌이 얼마나 넓게 퍼질지 모른다. 막대와 구슬의 연결 상태, 각 막대의 길이, 각 구슬의 무게가 주어질 때 완성된 모빌의 가로 폭을 구하라. 가로 폭은 모빌이 닿는 X좌표의 최댓값에서 최솟값을 뺀 값이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에 나무 막대의 수 $n$ ($1 \leq n \leq 100{,}000$)이 주어진다. 이어지는 $n$개의 줄 가운데 $i$번째 줄에는 $i$번 막대의 길이 $len$ ($1 \leq len \leq 1{,}000$)과, 왼쪽 끝과 오른쪽 끝에 매달린 물체를 나타내는 두 정수 $l$, $r$이 공백으로 구분되어 주어진다.

$-n \leq l \leq -1$이면 왼쪽 끝에 $-l$번 막대가 매달려 있다는 뜻이고, $1 \leq l \leq 100{,}000$이면 왼쪽 끝에 무게가 $l$인 구슬이 매달려 있다는 뜻이다. $r$는 오른쪽 끝을 가리킨다는 점만 다를 뿐 $l$과 같은 방식으로 읽으면 된다.

모든 막대는 1번 막대를 뿌리로 하는 하나의 연결된 구조에 속하고, 2번부터 $n$번까지의 막대는 각각 정확히 한 번씩 다른 막대의 끝에 매달린다.

각 테스트 케이스마다 한 줄에 모빌의 가로 폭을 출력한다. 소수점 아래 여섯 자리까지 반올림해 적고, 자리가 비면 0으로 채운다. 폭이 정확히 5라면 5.000000으로 출력한다.

막대가 수평을 유지하려면 실을 매단 지점을 기준으로 양쪽 토크가 같아야 한다. 길이가 $len$인 막대의 왼쪽에 걸린 무게를 $W_l$, 오른쪽에 걸린 무게를 $W_r$라 하면 매단 지점에서 왼쪽 끝까지의 거리는 $\dfrac{len \times W_r}{W_l + W_r}$, 오른쪽 끝까지의 거리는 $\dfrac{len \times W_l}{W_l + W_r}$이다.

막대에 걸린 무게는 그 막대 아래에 매달린 모든 구슬의 무게를 더한 값이다. 막대와 실은 무게가 0이므로 더하지 않는다.