All Tracks>Algorithms> Graphs> Depth First Search> Problem
Temporary Tree
★★★★★

4

5 votes
Graphs, Depth First Search, Algorithms
Problem

You are gifted a tree consisting of N vertices. There are two types of edges each with a weight val and denoted by a type value that is either 0 or 1. A pair (i,j), where i<j is called GOOD if, while traversing from vertex i to vertex j, we never pass through an edge of type 0. 

Your task is to calculate the sum of the path’s weight of all the GOOD pairs present in the tree. Print the final answer modulo 109+7.

Input Format:

  • The first line of input contains an integer T, denoting the number of test cases.
  • The first line of each test case contains the integer N.
  • The next N - 1 line contains four integers A, B, type and val where A and B represents the vertices of the tree, type represent the type of the edge and val define the edge weight.

Output format: 

For each test case, print an integer denoting the sum of the path's weight of all the GOOD pairs modulo 109+7.

Constraints:

1≤T≤101≤N≤1051≤A,B≤N0≤type≤10≤val≤1000

It is guaranteed that the input graph forms a tree. 

Sample Input
2
3
1 2 0 5
2 3 1 3
3 
1 2 1 5
1 3 1 7
Sample Output
3
24
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first test case, there is only one GOOD pair, i.e. (2, 3) and the weight of the edge is 3.

In the second test case, the GOOD pairs are (1, 2), (1, 3), and (2, 3), and the sum of weights for all the three paths are 5, 7, and 12. Thus, the output is 24.

Contributers:
Editor Image

?