Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ITREE - Nhãn của cây

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 .

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-04-27
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2018-09-12 11:15:14
nhật hào sạch
2017-12-29 00:31:29
ledacthuongvq
2017-12-06 10:47:07
nhật hào sạch
2017-09-09 10:09:34
vcl
2017-08-15 15:16:21
Mấy thanh niên cmt lừa tình v =.=
2017-05-21 20:04:51
vl nghe mấy thanh niên cmt :(
2016-06-14 16:55:27
bài này lừa tình dễ sợ

Last edit: 2016-06-14 17:12:16
2016-06-09 18:38:35
đề bài rất lừa tình :v ĐỘ CHÍNH XÁC ở đây là phải có 2 chữ số ở sau dấu phẩy :v
2015-06-20 16:13:07 there's no salvation for me...
hãy hiểu rằng bạn vất còn rất thông minh khi có 1 con ngu đọc đề bài thành tìm max :v
2013-09-08 16:21:02 a;slkfjasl;fkj
hay :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.