Minimum Weighted Subgraph With the Required Paths II

Hard

#3164Time: 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).

Algorithms

Depth-First Search

Data structures

Array Tree

Prompt

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] = [u_i, v_i, w_i] indicates that there is an edge between nodes u_i and v_i with weight w_i.

Additionally, you are given a 2D integer array queries, where queries[j] = [src1_j, src2_j, dest_j].

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 dest_j from both src1_j and src2_j 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 <= 10⁵
edges.length == n - 1
edges[i].length == 3
0 <= u_i, v_i < n
1 <= w_i <= 10⁴
1 <= queries.length <= 10⁵
queries[j].length == 3
0 <= src1_j, src2_j, dest_j < n
src1_j, src2_j, and dest_j are pairwise distinct.
The input is generated such that edges represents 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 variable total_weight = 0.
- Find the path from src1 to dest using a graph traversal like BFS or DFS. This involves keeping track of parent pointers and then backtracking from dest.
- 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 to total_weight.
- Find the path from src2 to dest using another traversal.
- Iterate through the edges of this second path, again adding the weight to total_weight only for new edges.
- The final total_weight is the answer for the current query.

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.

1// Helper methods to be part of a solution class.2// The main logic would iterate through queries and call solveQueryBruteForce.3 4private long solveQueryBruteForce(int src1, int src2, int dest, int n, java.util.List<java.util.List<int[]>> adj) {5    java.util.List<int[]> path1 = findPath(src1, dest, n, adj);6    java.util.List<int[]> path2 = findPath(src2, dest, n, adj);7 8    java.util.Set<String> uniqueEdges = new java.util.HashSet<>();9    long totalWeight = 0;10 11    for (int[] edge : path1) {12        int u = Math.min(edge[0], edge[1]);13        int v = Math.max(edge[0], edge[1]);14        if (uniqueEdges.add(u + "-" + v)) {15            totalWeight += edge[2];16        }17    }18    for (int[] edge : path2) {19        int u = Math.min(edge[0], edge[1]);20        int v = Math.max(edge[0], edge[1]);21        if (uniqueEdges.add(u + "-" + v)) {22            totalWeight += edge[2];23        }24    }25    return totalWeight;26}27 28private java.util.List<int[]> findPath(int start, int end, int n, java.util.List<java.util.List<int[]>> adj) {29    java.util.Map<Integer, int[]> parentMap = new java.util.HashMap<>(); // node -> {parent, weight_to_parent}30    java.util.Queue<Integer> q = new java.util.LinkedList<>();31    q.add(start);32    parentMap.put(start, new int[]{-1, 0});33 34    while (!q.isEmpty()) {35        int u = q.poll();36        if (u == end) break;37        for (int[] edge : adj.get(u)) {38            int v = edge[0];39            int w = edge[1];40            if (!parentMap.containsKey(v)) {41                parentMap.put(v, new int[]{u, w});42                q.add(v);43            }44        }45    }46    47    java.util.List<int[]> path = new java.util.ArrayList<>();48    int curr = end;49    while (parentMap.containsKey(curr) && parentMap.get(curr)[0] != -1) {50        int[] p_info = parentMap.get(curr);51        int p = p_info[0];52        int w = p_info[1];53        path.add(new int[]{p, curr, w});54        curr = p;55    }56    return path;57}

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.

This efficient approach leverages precomputation to answer queries quickly. It's based on a key mathematical property of trees: the total weight of the minimal subtree connecting three nodes (src1, src2, dest) can be calculated as (dist(src1, src2) + dist(src1, dest) + dist(src2, dest)) / 2. The distance dist(u, v) between any two nodes can be found efficiently using their Lowest Common Ancestor (LCA).

Algorithm

Preprocessing Phase (O(N log N)):
- Build an adjacency list representation of the tree from the input edges.
- Pick a root (e.g., node 0) and perform a DFS traversal.
- During DFS, for each node u, compute its depth[u], weighted distance from the root dist_from_root[u], and its parent up[u][0].
- After the DFS, populate the binary lifting table up[u][i] for i > 0 using the relation up[u][i] = up[up[u][i-1]][i-1].
Query Phase (O(log N) per query):
- For each query (src1, src2, dest):
  - Find the three Lowest Common Ancestors: lca12 = LCA(src1, src2), lca1d = LCA(src1, dest), and lca2d = LCA(src2, dest) using the binary lifting table.
  - Calculate the three path distances using the formula: dist(u, v) = dist_from_root[u] + dist_from_root[v] - 2 * dist_from_root[LCA(u, v)].
  - The final answer is (dist(src1, src2) + dist(src1, dest) + dist(src2, dest)) / 2.

Walkthrough

The distance formula is dist(u, v) = dist_root(u) + dist_root(v) - 2 * dist_root(LCA(u, v)), where dist_root(x) is the weighted distance from a fixed root to node x. To implement this, we first preprocess the tree.

Preprocessing: We perform a single DFS from an arbitrary root (e.g., node 0). This traversal computes the depth, distance from the root, and the immediate parent for every node. Then, we build a binary lifting table, up[u][i], which allows us to find the 2^i-th ancestor of any node u. Building this table takes O(N log N) time.
Querying: With the precomputed tables, an LCA query for two nodes u and v can be answered in O(log N) time. For each query (src1, src2, dest), we perform three LCA lookups and use the distance formula to find the three required path lengths. Finally, we apply the main formula to get the answer. This makes each query very fast.

1class Solution {2    private java.util.List<java.util.List<int[]>> adj;3    private int n;4    private int LOGN;5    private int[] depth;6    private long[] distFromRoot;7    private int[][] up;8 9    public long[] minWeight(int n, int[][] edges, int[][] queries) {10        this.n = n;11        this.LOGN = (int) (Math.log(n) / Math.log(2)) + 1;12        this.adj = new java.util.ArrayList<>();13        for (int i = 0; i < n; i++) {14            adj.add(new java.util.ArrayList<>());15        }16        for (int[] edge : edges) {17            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});18            adj.get(edge[1]).add(new int[]{edge[0], edge[2]});19        }20 21        this.depth = new int[n];22        this.distFromRoot = new long[n];23        this.up = new int[n][LOGN];24        for(int i=0; i<n; i++) java.util.Arrays.fill(up[i], -1);25 26        dfs(0, -1, 0, 0L);27        for (int j = 1; j < LOGN; j++) {28            for (int i = 0; i < n; i++) {29                if (up[i][j - 1] != -1) {30                    up[i][j] = up[up[i][j - 1]][j - 1];31                }32            }33        }34 35        long[] ans = new long[queries.length];36        for (int i = 0; i < queries.length; i++) {37            int src1 = queries[i][0];38            int src2 = queries[i][1];39            int dest = queries[i][2];40 41            long d12 = getDist(src1, src2);42            long d1d = getDist(src1, dest);43            long d2d = getDist(src2, dest);44 45            ans[i] = (d12 + d1d + d2d) / 2;46        }47        return ans;48    }49 50    private void dfs(int u, int p, int d, long currentDist) {51        depth[u] = d;52        distFromRoot[u] = currentDist;53        up[u][0] = p;54        for (int[] edge : adj.get(u)) {55            int v = edge[0];56            int w = edge[1];57            if (v != p) {58                dfs(v, u, d + 1, currentDist + w);59            }60        }61    }62 63    private int lca(int u, int v) {64        if (depth[u] < depth[v]) {65            int temp = u; u = v; v = temp;66        }67 68        for (int j = LOGN - 1; j >= 0; j--) {69            if (up[u][j] != -1 && depth[u] - (1 << j) >= depth[v]) {70                u = up[u][j];71            }72        }73 74        if (u == v) return u;75 76        for (int j = LOGN - 1; j >= 0; j--) {77            if (up[u][j] != -1 && up[v][j] != -1 && up[u][j] != up[v][j]) {78                u = up[u][j];79                v = up[v][j];80            }81        }82        return up[u][0];83    }84 85    private long getDist(int u, int v) {86        int lcaNode = lca(u, v);87        return distFromRoot[u] + distFromRoot[v] - 2 * distFromRoot[lcaNode];88    }89}

Complexity

Time

O((N + Q) * log N). Preprocessing the tree takes O(N log N) time. Each of the Q queries is then answered in O(log N) time.

Space

O(N log N), primarily for storing the binary lifting table `up`.

Trade-offs

Pros

Highly efficient and scalable for a large number of queries.
This is the standard and optimal solution for this class of problems on trees.

Cons

Implementation is more complex than the brute-force approach.
Requires understanding of advanced concepts like Lowest Common Ancestor and binary lifting.
Uses more memory due to the precomputation table.

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.

← Previous

Previous problem

Next problem