MTREE - Another Tree Problem

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


Cho một cây N đỉnh, N-1 cạnh. Mỗi cạnh được gán 1 số không âm. Trọng số của một đường đi là tích các số ghi trên cạnh. Trọng số của cây là tổng trọng số của mọi đường đi giữa mọi cặp đỉnh trên cây. Đường đi từ 2 nút A tới B và B tới A được coi là duy nhất, chỉ tính 1 lần.

Cho 1 cây, tính số dư trọng số của cây cho 1000000007.

Input

Dòng đầu là số đỉnh của cây - N (2 ≤ N ≤ 100 000). N-1 dòng tiếp theo mỗi dòng gồm 3 số nguyên A, B và W (1 ≤ A, B ≤ N, 0 ≤ W ≤ 1000) mô tả cạnh nối hai đỉnh A, B có trọng số W.

Output

Trọng số của cây theo module 1000000007.

Sample

input 
3 
3 2 100 
2 1 100 
 
output 
10200 
input 
4 
1 2 5 
1 3 5 
1 4 5 
 
output 
90 
input 
5 
1 2 2 
2 3 3 
4 3 2 
5 3 2 
 
output 
55
Note : làm quen QHD trên cây, hoặc vừa DFS vừa tính toán - tính ứng dụng cao
Task PUTEVI : Croatia Contest - Final Exam 08

Được gửi lên bởi:psetter
Ngày:2009-02-28
Thời gian chạy:1s
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
Nguồn bài:COI 08

hide comments
2021-05-27 18:02:11
Tham khảo: https://vnspoj.github.io/problems/MTREE
2018-02-25 18:18:11 Sơn Tùng M-TP
Gợi ý chút cho những bạn muốn xem: Sum of Products in a root node + tính toán cộng dồn theo từng node. Cẩn thận các phép toán số học.
2017-12-28 03:18:00
Quên cái long long mất mịa 1 đấm =.=
frostpixel aka.How 2 AC
2017-12-25 02:16:15
ledacthuongvq
2017-12-17 10:56:53
AE mod cẩn thận :))
2017-12-07 03:35:16
nhật hào sạch
2017-05-28 04:41:52


Last edit: 2017-05-28 04:42:25
2017-03-12 10:13:28
ai làm được r chỉ với
2015-09-25 19:05:33 Nguyễn Vĩnh Thịnh
cái mod kia làm khó quá T.T
2009-03-06 23:30:59 dhkhtn
Can than phep toan so hoc.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.