Minimum Weighted Subgraph With the Required Paths II
HardPrompt
You are given an undirected weighted tree with n nodes, numbered from 0 to n - 1. It is represented by a 2D integer array edges of length n - 1, where edges[i] = [ui, vi, wi] indicates that there is an edge between nodes ui and vi with weight wi.
Additionally, you are given a 2D integer array queries, where queries[j] = [src1j, src2j, destj].
Return an array answer of length equal to queries.length, where answer[j] is the minimum total weight of a subtree such that it is possible to reach destj from both src1j and src2j using edges in this subtree.
A subtree here is any connected subset of nodes and edges of the original tree forming a valid tree.
Example 1:
Input: edges = [[0,1,2],[1,2,3],[1,3,5],[1,4,4],[2,5,6]], queries = [[2,3,4],[0,2,5]]
Output: [12,11]
Explanation:
The blue edges represent one of the subtrees that yield the optimal answer.
-
answer[0]: The total weight of the selected subtree that ensures a path fromsrc1 = 2andsrc2 = 3todest = 4is3 + 5 + 4 = 12. -
answer[1]: The total weight of the selected subtree that ensures a path fromsrc1 = 0andsrc2 = 2todest = 5is2 + 3 + 6 = 11.
Example 2:
Input: edges = [[1,0,8],[0,2,7]], queries = [[0,1,2]]
Output: [15]
Explanation:
answer[0]: The total weight of the selected subtree that ensures a path fromsrc1 = 0andsrc2 = 1todest = 2is8 + 7 = 15.
Constraints:
3 <= n <= 105edges.length == n - 1edges[i].length == 30 <= ui, vi < n1 <= wi <= 1041 <= queries.length <= 105queries[j].length == 30 <= src1j, src2j, destj < nsrc1j,src2j, anddestjare pairwise distinct.- The input is generated such that
edgesrepresents a valid tree.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the problem statement for each query. It finds the two required paths, from src1 to dest and src2 to dest, and then computes the total weight of their union. This is straightforward but inefficient due to redundant computations across queries.
Algorithm
- For each query
(src1, src2, dest):- Initialize an empty set,
union_edges, to store unique edges and a variabletotal_weight = 0. - Find the path from
src1todestusing a graph traversal like BFS or DFS. This involves keeping track of parent pointers and then backtracking fromdest. - Iterate through the edges of this path. For each edge, add it to
union_edges. If the edge was not already in the set, add its weight tototal_weight. - Find the path from
src2todestusing another traversal. - Iterate through the edges of this second path, again adding the weight to
total_weightonly for new edges. - The final
total_weightis the answer for the current query.
- Initialize an empty set,
Walkthrough
The core idea is to treat each query independently. For a given query (src1, src2, dest), we need to identify the set of edges that form the paths P(src1, dest) and P(src2, dest). The union of these edges forms the minimal required subtree.
We can use a graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS) to find these paths. For instance, to find P(src1, dest), we start a traversal from src1. During the traversal, we keep track of the parent of each visited node. Once dest is reached, we can reconstruct the path by backtracking from dest to src1 using the parent pointers. The same process is repeated for P(src2, dest). To get the total weight, we collect all unique edges from both paths and sum their weights. A HashSet is suitable for storing the unique edges to avoid double-counting the edges in the overlapping part of the paths.
// Helper methods to be part of a solution class.// The main logic would iterate through queries and call solveQueryBruteForce. private long solveQueryBruteForce(int src1, int src2, int dest, int n, java.util.List<java.util.List<int[]>> adj) { java.util.List<int[]> path1 = findPath(src1, dest, n, adj); java.util.List<int[]> path2 = findPath(src2, dest, n, adj); java.util.Set<String> uniqueEdges = new java.util.HashSet<>(); long totalWeight = 0; for (int[] edge : path1) { int u = Math.min(edge[0], edge[1]); int v = Math.max(edge[0], edge[1]); if (uniqueEdges.add(u + "-" + v)) { totalWeight += edge[2]; } } for (int[] edge : path2) { int u = Math.min(edge[0], edge[1]); int v = Math.max(edge[0], edge[1]); if (uniqueEdges.add(u + "-" + v)) { totalWeight += edge[2]; } } return totalWeight;} private java.util.List<int[]> findPath(int start, int end, int n, java.util.List<java.util.List<int[]>> adj) { java.util.Map<Integer, int[]> parentMap = new java.util.HashMap<>(); // node -> {parent, weight_to_parent} java.util.Queue<Integer> q = new java.util.LinkedList<>(); q.add(start); parentMap.put(start, new int[]{-1, 0}); while (!q.isEmpty()) { int u = q.poll(); if (u == end) break; for (int[] edge : adj.get(u)) { int v = edge[0]; int w = edge[1]; if (!parentMap.containsKey(v)) { parentMap.put(v, new int[]{u, w}); q.add(v); } } } java.util.List<int[]> path = new java.util.ArrayList<>(); int curr = end; while (parentMap.containsKey(curr) && parentMap.get(curr)[0] != -1) { int[] p_info = parentMap.get(curr); int p = p_info[0]; int w = p_info[1]; path.add(new int[]{p, curr, w}); curr = p; } return path;}Complexity
Time
O(Q * N), where Q is the number of queries and N is the number of nodes. Each query involves two full graph traversals, each taking up to O(N) time.
Space
O(N), where N is the number of nodes. Each query requires space for the traversal data structures (e.g., visited set, parent pointers, queue/stack).
Trade-offs
Pros
Simple to conceptualize and implement.
Requires no complex data structures or precomputation.
Cons
Extremely inefficient for a large number of queries, as it recomputes paths from scratch every time.
Will result in a 'Time Limit Exceeded' (TLE) verdict for the given problem constraints.
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.