ITREE - Nhãn của cây
Giới hạn- Thời gian: 0.023s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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.00Giải thích : Phương án tối ưu là A[1] = 1 , A[2] = 0.5 , A[3] = 0 , A[4] = 0 .
- Người up: hard7771988