#863. SUMTREE - Tổng trên cây

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một cây có N đỉnh, các đỉnh được đánh số từ 1 đến N , các cạnh đều có trọng số, hãy tính tổng khoảng cách từ một đỉnh u đến các đỉnh còn lại trên cây.

Dữ liệu vào:

  • Dòng đầu tiên chứa số N là số đỉnh của cây;
  • N - 1 dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w biểu diễn cạnh nối giữa u v có trọng số là w\ (1\le u, v \le N \le 10^6, u \ne v, 1\le w\le 10^6) .

Dữ liệu ra:

  • Một dòng gồm N số, số thứ u là tổng khoảng cách từ đỉnh u đến các đỉnh còn lại trên đồ thị.

Ví dụ:

Dữ liệu vào:

4
1 4 7
2 3 5
4 2 6

Dữ liệu ra:

38
24
34
24

Dữ liệu vào:

4
1 2 2
3 1 4
4 3 5

Dữ liệu ra:

15
19
15
25