Giải bài trực tuyến

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/itree

Cho đồ thị cây có trọng số gồm N đỉnh , các đỉnh được đánh số từ 1 -> N . Gốc của cây là đỉnh 1 . Cha của đỉnh u là 1 đỉnh có số hiệu nhỏ hơn u . Mỗi đỉnh có một nhãn là 1 số thực A[i] . Trong đó nhãn của đỉnh 1 bằng 1 và nhãn của đỉnh lá bằng 0 . Biết rằng A[v] ≤ A[u] nếu v là con của u .
Giá trị của 1 cây = Tổng ( ( A[u] – A[v] ) * Trọng số cạnh (u,v) , với u là cha của v )
Bây giờ người ta cho biết các cạnh của đồ thị và trọng số của các cạnh này nhưng không cho biết các A[i]. Hãy tính xem giá trị của cây thấp nhất là bao nhiêu.

Input

Dòng 1 là số nguyên T là số bộ test . ( 1 ≤ T ≤ 50 ) . T nhóm dòng tiếp theo mô tả từng bộ test . Mỗi bộ test sẽ có cấu trúc như sau :
Dòng 1 : số nguyên dương N ( 1 ≤ N ≤ 1000 ) .
Từ dòng 2 -> dòng N : dòng thứ i gồm 2 số nguyên dương u và c ( 1 ≤ u < i , 0 ≤ c ≤ 1000 ) cho biết cha của nút i là nút u và cạnh nối (u,i) có trọng số là c .

Output

Với mỗi test ghi ra giá trị thấp nhất có thể đạt được của cây trên 1 dòng với độ chính xác là 2 chữ số sau dấu chấm.

Example

Input:
1
4
1 1
1 2
2 1

Output:
3.00

Giải thích : Phương án tối ưu là A[1] = 1 , A[2] = 0.5 , A[3] = 0 , A[4] = 0 .