Temporary Tree

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’.

Approach: We will reduce the time complexity by checking for all the pairs by fixing the value of ‘i’ in pairs (i, j) by forming a tree with the root node as ‘i’. Thus, if we can visit any vertex whose value is less than ‘i’, we can say that they form a GOOD pair and increment the answer by the path’s weight. And for creating a tree, we can use BFS as we also need distance parameters simultaneously to add the path’s weight in the final answer.

 

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:
   • For forming a Tree, we will call the DFS function.
     • ‘ans’ value increases by ‘formTree(n, i, graph, mod)’.
   • ‘ans’ equals ‘ans’ mod 10^9 + 7.
6. Return the final answer ‘ans’.

formTree(n, index, graph, mod):

1. Initialize a variable ‘ans’ as 0 to store the answer.
2. Initialize a vector ‘visited’ of size ‘N’ + 1 with ‘false’.
3. Initialize a queue ‘q’ for storing all the vertices and path’s weight.
4. Push a pair of ‘index’ and 0 in the queue ‘q’.
5. Mark ‘index’ as present in the ‘visited’ vector.
6. Run a loop while ‘q’ is not empty:
   • Initialize ‘top’ with the front of ‘q’ and pop that element from the queue.
   • Assign ‘currNode’ and ‘currWeight’ as  ‘top.first’ and ‘top.second’ respectively.
   • If ‘currNode’ is greater than ‘index’ it means they form a GOOD pair.
     • The value of ‘ans’ increases by ‘currWeight’.
     • ‘ans’ equals ‘ans’ mod 10^9 + 7.
   • Iterate a loop ‘itr’ to add all vertices that are connected with ‘currNode’.
     • Initialize ‘nextNode’ with ‘itr.first’.
     • Initialize ‘weight’ with ‘itr.second’.
     • If ‘visited[nextNode]’ equals ‘false’:
       • Mark ‘nextNode’ as visited in the ‘visited’ vector.
         • Assign ‘visited[nextNode]’ as ‘true’.
       • Push a pair of ‘nextNode’ and ‘currWeight’ + ‘weight’ in the queue ‘q’.
7. Return the final answer ‘ans’.

Approach: We know that if an edge is removed from a tree, it breaks a tree into two trees, and the number of connected components increases by 1. Thus, a vertex in one connected component cannot visit the vertex present in other connected components. So, we will run a loop to check if all vertices are visited or not, and the vertex that is not visited will be called and will make a connected component of it. Each edge in that corresponding component will contribute to the final answer by “subtree[v] * (size - subtree[v])” times the weight of that edge.

 

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. Initialize a vector ‘visited’ of size ‘N’ + 1 with ‘false’.
6. Run a loop ‘i’ from 1 to ‘N’:
   • If ‘visited[i]’ equals ‘false’:
     • The value of ‘ans’ increases by ‘temporaryBinaryTreeHelper(n, i, graph, visited, mod)’.
     • ‘ans’ equals ‘ans’ mod 10^9 + 7.
7. Return the final answer ‘ans’.

temporaryBinaryTreeHelper(n, start, graph, visited, mod):

1. Initialize a variable ‘size’ as 0 to store the size of the current connected component.
2. Initialize a vector ‘subtree’ of size ‘N’ + 1 with ‘0’.
3. Initialize a vector ‘allAcceptedEdges’ to store all the pairs of edge weight and subtree value present in the current connected component.
4. Call the ‘dfs(graph, start, visited, subtree, size, allAcceptedEdges)’ function.
5. Initialize a variable ‘ans’ as 0 to store the answer.
6. Iterate a loop ‘itr’ to add all values of ‘allAcceptedEdges’.
   • Initialize ‘weight’ with ‘itr.first’.
   • Initialize ‘currentSubtreeValue’ with ‘itr.second’.
   • ‘ans’ value increases by ‘weight’ * ‘currSubtreeValue’ * (‘size’ - ‘currSubtreeValue’).
   • ‘ans’ equals ‘ans’ mod 10^9 + 7.
7. Return the final answer ‘ans’.
    

dfs(graph, index, visited, subtree, size, allAcceptedEdges):

1. Mark ‘index’ as present in the ‘visited’ vector.
2. Increment value of ‘size’ by 1.
3. Increment value of ‘subtree[size]’ by 1.
4. Iterate a loop ‘itr’ to add all vertices that are connected with ‘currNode’.
   • Initialize ‘node’ with ‘itr.first’.
   • Initialize ‘weight’ with ‘itr.second’.
   • If ‘visited[node]’ equals ‘false’:
     • Call ‘dfs(graph, node, visited, subtree, size,allAcceptedEdges)’ recursively.
     • Push a pair of ‘weight’ and ‘subtree[node]’ in the vector ‘allAcceptedEdges’.
     • Increment value of ‘subtree[index]’ by ‘subtree[node]’.
5. Return the final answer ‘ans’.