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.|

HARBINGE - Harbingers

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/harbinge


Ngày xửa ngày xưa, có  N thị trấn kiểu trung cổ trong khu tự trị Moldavian. Các thị trấn này được đánh số từ 1 đến N. Thị trấn 1 là thủ đô. Các thị trấn được nối với nhau bằng N-1 con đường hai chiều, mỗi con đường có độ dài được đo bằng km. Có duy nhất một tuyến đường nối giữa hai điểm bất kỳ (đồ thị các con đường là hình cây). Mỗi thị trấn không phải trung tâm có một người truyền tin.

Khi một thị trấn bị tấn công, tình hình chiến sự cần được báo về thủ đô càng sớm càng tốt. Một thông điệp được truyền bằng các người truyền tin. Mỗi người truyền tin được đặc trưng bởi lượng thời gian khởi động và vận tốc không đổi sau khi xuất phát.

Thông điệp luôn được truyền trên con đường ngắn nhất đến trung tâm. Ban đầu, thông tin chiến sự được đưa cho người truyền tin tại thị trấn bị tấn công. Từ thị trấn đó người truyền tin sẽ đi theo con đường về gần thủ đô hơn. Khi đến một thị trấn mới, người truyền tin có thể đi tiếp hoặc chuyển cho người truyền tin tại thị trấn mới vừa đến. Lưu ý rằng khi chuyển sang người truyền tin mới thì người này cần một lượng thời gian để khởi động rồi mới đi chuyển tin. Như vậy, thông điệp sẽ được chuyển bằng một số người truyền tin trước khi đến thủ đô.

Hãy xác định thời gian ít nhất cần chuyển tin từ các thị trấn về thủ đô.

Input

Dòng đầu ghi số N. Trong N-1 dòng tiếp theo, mỗi dòng ghi ba số u, vd thể một con đường nối từ u đến v với độ dài bằng d. Trong N-1 dòng tiếp theo, dòng thứ i ghi hai số SiVi thể hiện thời gian cần để khởi động và số lượng phút để đi được 1 km của người truyền tin ở thị trấn (i+1).

Output

Ghi N-1 số trên một dòng. Số thứ i thể hiện thời gian ít nhất cần truyền tin từ thành phố (i+1) về thủ đô.

INPUT

5

1 2 20

2 3 12

2 4 1

4 5 3

26 9

1 10

500 2

2 30

OUTPUT

206 321 542 328

 

Giới hạn:

  • 3 ≤ N ≤ 100 000, 0 ≤ Si ≤ 109, 1 ≤ Vi ≤ 109
  • Độ dài không vượt quá 10 000.

Được gửi lên bởi:sieunhan
Ngày:2011-03-20
Thời gian chạy:0.808s
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ừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:CEOI 2009

hide comments
2017-03-16 10:55:55


Last edit: 2017-03-16 12:53:06
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.