Watch 5 video solutions for Minimum Weighted Subgraph With the Required Paths II, a hard level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by Amit Dhyani has 1,003 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 from src1 = 2 and src2 = 3 to dest = 4 is 3 + 5 + 4 = 12.
answer[1]: The total weight of the selected subtree that ensures a path from src1 = 0 and src2 = 2 to dest = 5 is 2 + 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 from src1 = 0 and src2 = 1 to dest = 2 is 8 + 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, and destj are pairwise distinct.edges represents a valid tree.Problem Overview: You are given a weighted structure where certain paths must exist between specific nodes. The task is to select a subgraph with the minimum total weight that still preserves all required paths. Because the structure forms a tree and the number of required path constraints is small, the problem becomes a state-compression dynamic programming problem over the tree.
Approach 1: Brute Force Subgraph Enumeration (Exponential Time, Exponential Space)
The naive idea is to enumerate every possible subset of edges and check whether the resulting subgraph still satisfies all required paths. For each subset, run connectivity checks using DFS to verify that every required pair of nodes remains connected. Track the total edge weight and keep the minimum valid configuration. This approach requires checking up to 2^E edge subsets, and each validation costs O(n) using DFS, resulting in roughly O(2^E * n) time and O(n) auxiliary space. It quickly becomes infeasible even for moderate tree sizes but helps clarify the constraint that the chosen subgraph must preserve multiple connectivity requirements.
Approach 2: Tree Dynamic Programming with Bitmask States (O(n · 2^k) Time, O(n · 2^k) Space)
The optimized solution leverages the fact that the graph is a tree and the number of required paths k is small. Assign each required path an index and represent satisfied requirements using a k-bit mask. Perform a Depth-First Search from an arbitrary root. For every node, maintain a DP table where dp[node][mask] represents the minimum cost of the subtree that satisfies the set of path constraints encoded in mask.
During DFS, process children one by one and merge their DP states with the current node using bitmask transitions. When combining two states, compute the union of their masks with a bitwise OR operation and add the edge weight if the edge must be included to maintain connectivity. This is a classic state-compression technique using Bit Manipulation combined with subtree aggregation on a Tree. Because each node processes up to 2^k masks and merges with children states, the total complexity becomes O(n · 2^k) time with O(n · 2^k) memory.
Recommended for interviews: Interviewers expect the tree DP with bitmask compression. Starting with brute force demonstrates understanding of the constraint space, but the optimal solution shows you recognize two key signals: the structure is a tree and the number of required conditions is small enough for state compression. Combining DFS traversal with bitmask DP is the standard pattern for these problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Edge Subsets | O(2^E · n) | O(n) | Conceptual baseline or when graph size is extremely small |
| Tree DP with Bitmask + DFS | O(n · 2^k) | O(n · 2^k) | Optimal solution when the structure is a tree and required path count k is small |
| State Compression with Child Merging | O(n · 2^k) | O(2^k) | Memory-optimized variant that reuses DP buffers during DFS |