Temporary Tree

Hard
0/120
Average time to solve is 45m
profile
Contributed by
7 upvotes
Asked in company
Gartner

Problem statement

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 vertice 'i' to vertice '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. Return the final answer modulo 10^9 + 7.

Example: 
Input: ‘N’ = 3 and edges are [{1, 2, 0, 5}, {2, 3, 1, 3}] and edges are given in format {u, v, type, weight}.
Output: 3
Explanation: There is only one GOOD pair, i.e. {2, 3} and the weight of the edge is 3.
Detailed explanation ( Input/output format, Notes, Images )
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 weight of all the paths of all the GOOD pairs.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 5
1 <= ‘N’ <= 10^5
1 <= ‘U’, ‘V’ <= ‘N’
0 <= ‘VAL’ <= 10^3

It is guaranteed that the input graph forms a tree.

Time Limit: 1 sec
Sample Input 1 :
1
3 
1 2 1 5
1 3 1 7
Sample Output 1 :
24
Explanation Of Sample Input 1 :
In the first 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.
Sample Input 2 :
2
2
1 2 0 10
2
1 2 1 10
Sample Output 2 :
0
10
Hint

Try to check all the pairs, include the pairs that satisfy the given condition, and add them to the answer.

Approaches (3)
Brute Force Approach

Approach: As we are given that it forms a tree, we know that there will only be one path from one node to another. Thus, we will run two loops and check for all the pairs whether the pair is GOOD or not. If we don’t traverse through an edge having ‘TYPE’ 0, we will include the weight of the entire path in our final answer. Also, we can deduct from the problem statement that if the ‘TYPE’ of an edge is 0, then it is good to ignore it as we can’t include that edge in our final answer. And for calculating the weighted path between both the path, we can use BFS.
 

Algorithm : 

  1. Initialize a variable ‘ans’ as 0 to store the answer.
  2. Assign variable ‘mod’ as 10^9 + 7.
  3. To form a graph, we will make a vector of vectors having pairs where the first element will be the vertex and the second will be the weight of the edge.
  4. Run a loop ‘i’ from 0 to ‘N’ - 1 and add all the edges in the graph.
    • As we know, edges with ‘TYPE’ 0 will not contribute and will not get added to the graph.
    • We will add the edge in both the vectors having index ‘u’ and ‘v’.
  5. Run a loop ‘i’ from 1 to ‘N’ - 1:
    • Run a loop ‘j’ from ‘i’ + 1 to ‘N’:
      • The value of ‘ans’ increases by the sum of the path’s weight from vertex ‘i’ to vertex ‘j’ by calling a BFS function.
      • ‘ans’ equals ‘ans’ mod 10^9 + 7.
  6. Return the final answer ‘ans’.
Time Complexity

O(N^3), where ‘N’ is the number of nodes in the given tree.
 

Since we are iterating two loops to check all possible pairs, it will take O(N^2) time, and for each pair, we are calling the BFS function, which takes at max O(N) time for calculating the path’s weight. Thus, the overall time complexity is O(N^3).

Space Complexity

O(N), where ‘N’ is the number of nodes in the given tree.
 

Since we are making the graph at the start, which will have ‘N’ - 1 edge and consume O(N) space, the overall Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Temporary Tree
Full screen
Console