Simple Path
当前没有测试数据。
You will be given a weighted rooted tree, where root is node 1. For each subtree of that tree, you will have to compute the summation of lengths of all possible simple paths present in that subtree. Eventually you need to print the summation of those values modulo 1000000007.
Image of the tree in the first sample is given below.
Input Specification
First line of input will contain an integer T (1 <= T <= 10) denoting the number of test cases. Each test case will begin with an integer N (1<= N <=100000), indicating number of nodes. The following N-1 lines will have three integers each, U (1 <= U <= N), V (1 <= V <= N), W (1 <= W <= 1000000000), which denotes that there is an edge in the tree from node U to node V having W weight.
Input File is large. Use fast I/O methods.
Output Specification
For each test case, print the case number then print the answer to the problem modulo 1000000007 in separate lines.
Sample I/O
|
Sample Input |
Sample Output |
|
2 7 1 2 3 1 3 2 2 4 1 2 5 4 3 6 6 3 7 8 6 1 2 3 1 3 2 1 4 4 3 5 7 3 6 1 |
Case 1: 212 Case 2: 109 |
Explanation of Sample I/O
Explanation of the 1st sample:
Summation of lengths of all possible sample paths for each subtree is given below:
1: 174
2: 10
3: 28
4: 0
5: 0
6: 0
7: 0
Explanation of the 2nd sample:
Summation of lengths of all possible sample paths for each subtree is given below:
1: 93
2: 0
3: 16
4: 0
5: 0
6: 0