MTREE  Another Tree Problem
English  Vietnamese 
As you are bound to know by now, a tree is a connected graph consisting of N vertices and N−1 edges. Trees also have the property of there being exactly a single unique path between any pair of vertices. You will be given a tree in which every edge is assigned a weight – a non negative integer. The weight of a path is the product of the weights of all edges on the path. The weight of the tree is the sum of the weights of all paths in the tree. Paths going in opposite directions (A to B and B to A) are considered the same and, when calculating the weight of a tree, are counted only once.
Write a program that, given a tree, calculates its weight modulo 1000000007.
Input
The first line contains the integer N (2 ≤ N ≤ 100 000), the number of vertices in the tree. The vertices are numbered 1 to N. Each of the following N−1 contains three integers A, B and W (1 ≤ A, B ≤ N, 0 ≤ W ≤ 1000) describing one edge. The edge connects vertices A and B, and its weight is W.
Output
Output the weight of the tree, modulo 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
hide comments
dung04052000:
20160813 16:14:56
Hi


aghori_sadhu:
20160714 15:21:39
Cool problem :)


linkret:
20160629 09:25:19
Tigran Galstyan, COI is Croatian Olimpiad in Informatics 

Jens Stimpfle:
20140715 22:04:01
Warning for those parsing integers themselves: Input file has DOS line endings. 

Tigran Galstyan:
20140424 10:36:08
Can anyone tell me what contest is COI?? 

Igor:
20130702 18:12:13
Can't figure out what is wrong with my solution. Also wrote an O(N^3) bruteforce solver and results match. Could anyone look at my submission 9592767? 

guliashvili:
20130209 16:19:03
Srivatsan B


Shinken Yellow:
20120608 16:43:36
I am Vietnamese.


mike!:
20120604 23:31:26
Last edit: 20120616 17:36:15 
Added by:  ~!(*(@*!@^& 
Date:  20090228 
Time limit:  0.113s0.226s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COI 08 