Another Tree Problem

View as PDF

Submit solution


Points: 0.31 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
COI 08
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 \leq N \leq 100\,000)~.
  • N-1 dòng tiếp theo mỗi dòng gồm ~3~ số nguyên ~A~, ~B~ và ~W~ ~(1 \leq A~, ~B \leq N~, ~0 \leq W \leq 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 1

3
3 2 100
2 1 100

Sample Output 1

10200

Sample Input 2

4 
1 2 5 
1 3 5 
1 4 5

Sample Output 2

90

Sample Input 3

5 
1 2 2 
2 3 3 
4 3 2 
5 3 2

Sample Output 3

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.