# Minimum Weighted Subgraph With the Required Paths II
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-weighted-subgraph-with-the-required-paths-ii
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Tree
---
## Problem
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.

![](https://assets.glich.co/dsa/minimum-weighted-subgraph-with-the-required-paths-ii/image0.jpg)

* `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:**

![](https://assets.glich.co/dsa/minimum-weighted-subgraph-with-the-required-paths-ii/image1.jpg)

* `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 <= 105`
* `edges.length == n - 1`
* `edges[i].length == 3`
* `0 <= ui, vi < n`
* `1 <= wi <= 104`
* `1 <= queries.length <= 105`
* `queries[j].length == 3`
* `0 <= src1j, src2j, destj < n`
* `src1j`, `src2j`, and `destj` are pairwise distinct.
* The input is generated such that `edges` represents a valid tree.

# Approaches
## Brute-Force Path Finding per Query
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.
**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).
**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.
### Explanation
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.

```java
// 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;
}
```
### 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.

## Optimized Approach using LCA and Distance Formula
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).
**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`.
**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.
### Explanation
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.

1.  **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.

2.  **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.

```java
class Solution {
    private java.util.List<java.util.List<int[]>> adj;
    private int n;
    private int LOGN;
    private int[] depth;
    private long[] distFromRoot;
    private int[][] up;

    public long[] minWeight(int n, int[][] edges, int[][] queries) {
        this.n = n;
        this.LOGN = (int) (Math.log(n) / Math.log(2)) + 1;
        this.adj = new java.util.ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new java.util.ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
            adj.get(edge[1]).add(new int[]{edge[0], edge[2]});
        }

        this.depth = new int[n];
        this.distFromRoot = new long[n];
        this.up = new int[n][LOGN];
        for(int i=0; i<n; i++) java.util.Arrays.fill(up[i], -1);

        dfs(0, -1, 0, 0L);
        for (int j = 1; j < LOGN; j++) {
            for (int i = 0; i < n; i++) {
                if (up[i][j - 1] != -1) {
                    up[i][j] = up[up[i][j - 1]][j - 1];
                }
            }
        }

        long[] ans = new long[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int src1 = queries[i][0];
            int src2 = queries[i][1];
            int dest = queries[i][2];

            long d12 = getDist(src1, src2);
            long d1d = getDist(src1, dest);
            long d2d = getDist(src2, dest);

            ans[i] = (d12 + d1d + d2d) / 2;
        }
        return ans;
    }

    private void dfs(int u, int p, int d, long currentDist) {
        depth[u] = d;
        distFromRoot[u] = currentDist;
        up[u][0] = p;
        for (int[] edge : adj.get(u)) {
            int v = edge[0];
            int w = edge[1];
            if (v != p) {
                dfs(v, u, d + 1, currentDist + w);
            }
        }
    }

    private int lca(int u, int v) {
        if (depth[u] < depth[v]) {
            int temp = u; u = v; v = temp;
        }

        for (int j = LOGN - 1; j >= 0; j--) {
            if (up[u][j] != -1 && depth[u] - (1 << j) >= depth[v]) {
                u = up[u][j];
            }
        }

        if (u == v) return u;

        for (int j = LOGN - 1; j >= 0; j--) {
            if (up[u][j] != -1 && up[v][j] != -1 && up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
        return up[u][0];
    }

    private long getDist(int u, int v) {
        int lcaNode = lca(u, v);
        return distFromRoot[u] + distFromRoot[v] - 2 * distFromRoot[lcaNode];
    }
}
```
### 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`.