In this guide, you will get 3553. Minimum Weighted Subgraph With the Required Paths II LeetCode Solution with the best time and space complexity. The solution to Minimum Weighted Subgraph With the Required Paths II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Weighted Subgraph With the Required Paths II
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.
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.
3553. Minimum Weighted Subgraph With the Required Paths II LeetCode Solution in C++
class Solution {
public:
// Similar to 2846. Minimum Edge Weight Equilibrium Queries in a Tree
vector<int> minimumWeight(vector<vector<int>>& edges,
vector<vector<int>>& queries) {
const int n = edges.size() + 1;
const int m = ceil(log2(n));
vector<int> ans;
vector<vector<pair<int, int>>> graph(n);
// jump[i][j] := the 2^j-th ancestor of i
vector<vector<int>> jump(n, vector<int>(m));
// depth[i] := the depth of i
vector<int> depth(n);
// dist[i] := the distance from root to i
vector<int> dist(n);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
const int w = edge[2];
graph[u].emplace_back(v, w);
graph[v].emplace_back(u, w);
}
dfs(graph, 0, /*prev=*/-1, jump, depth, dist);
for (int j = 1; j < m; ++j)
for (int i = 0; i < n; ++i)
jump[i][j] = jump[jump[i][j - 1]][j - 1];
for (const vector<int>& query : queries) {
const int src1 = query[0];
const int src2 = query[1];
const int dest = query[2];
ans.push_back((distance(src1, src2, jump, depth, dist) +
distance(src1, dest, jump, depth, dist) +
distance(src2, dest, jump, depth, dist)) /
);
}
return ans;
}
private:
void dfs(const vector<vector<pair<int, int>>>& graph, int u, int prev,
vector<vector<int>>& jump, vector<int>& depth, vector<int>& dist) {
for (const auto& [v, w] : graph[u]) {
if (v == prev)
continue;
jump[v][0] = u;
depth[v] = depth[u] + 1;
dist[v] = dist[u] + w;
dfs(graph, v, u, jump, depth, dist);
}
}
// Returns the lca(u, v) by binary jump.
int getLCA(int u, int v, const vector<vector<int>>& jump,
const vector<int>& depth) {
// v is always deeper than u.
if (depth[u] > depth[v])
return getLCA(v, u, jump, depth);
// Jump v to the same height of u.
for (int j = 0; j < jump[0].size(); ++j)
if (depth[v] - depth[u] >> j & 1)
v = jump[v][j];
if (u == v)
return u;
// Jump u and v to the node right below the lca.
for (int j = jump[0].size() - 1; j >= 0; --j)
if (jump[u][j] != jump[v][j]) {
u = jump[u][j];
v = jump[v][j];
}
return jump[u][0];
}
// Returns the distance between u and v.
int distance(int u, int v, const vector<vector<int>>& jump,
const vector<int>& depth, const vector<int>& dist) {
const int lca = getLCA(u, v, jump, depth);
return dist[u] + dist[v] - 2 * dist[lca];
}
}; /* code provided by PROGIEZ */
3553. Minimum Weighted Subgraph With the Required Paths II LeetCode Solution in Java
class Solution {
// Similar to 2846. Minimum Edge Weight Equilibrium Queries in a Tree
public int[] minimumWeight(int[][] edges, int[][] queries) {
final int n = edges.length + 1;
final int m = (int) Math.ceil(Math.log(n) / Math.log(2));
int[] ans = new int[queries.length];
List<Pair<Integer, Integer>>[] graph = new List[n];
// jump[i][j] := the 2^j-th ancestor of i
int[][] jump = new int[n][m];
// depth[i] := the depth of i
int[] depth = new int[n];
// dist[i] := the distance from root to i
int[] dist = new int[n];
for (int i = 0; i < n; ++i)
graph[i] = new ArrayList<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
final int w = edge[2];
graph[u].add(new Pair<>(v, w));
graph[v].add(new Pair<>(u, w));
}
dfs(graph, 0, /*prev=*/-1, jump, depth, dist);
for (int j = 1; j < m; ++j)
for (int i = 0; i < n; ++i)
jump[i][j] = jump[jump[i][j - 1]][j - 1];
for (int i = 0; i < queries.length; ++i) {
final int src1 = queries[i][0];
final int src2 = queries[i][1];
final int dest = queries[i][2];
ans[i] = (distance(src1, src2, jump, depth, dist) + distance(src1, dest, jump, depth, dist) +
distance(src2, dest, jump, depth, dist)) /
;
}
return ans;
}
private void dfs(List<Pair<Integer, Integer>>[] graph, int u, int prev, int[][] jump, int[] depth,
int[] dist) {
for (Pair<Integer, Integer> pair : graph[u]) {
final int v = pair.getKey();
final int w = pair.getValue();
if (v == prev)
continue;
jump[v][0] = u;
depth[v] = depth[u] + 1;
dist[v] = dist[u] + w;
dfs(graph, v, u, jump, depth, dist);
}
}
// Returns the lca(u, v) by binary jump.
private int getLCA(int u, int v, int[][] jump, int[] depth) {
// v is always deeper than u.
if (depth[u] > depth[v])
return getLCA(v, u, jump, depth);
// Jump v to the same height of u.
for (int j = 0; j < jump[0].length; ++j)
if ((depth[v] - depth[u] >> j & 1) == 1)
v = jump[v][j];
if (u == v)
return u;
// Jump u and v to the node right below the lca.
for (int j = jump[0].length - 1; j >= 0; --j)
if (jump[u][j] != jump[v][j]) {
u = jump[u][j];
v = jump[v][j];
}
return jump[u][0];
}
// Returns the distance between u and v.
private int distance(int u, int v, int[][] jump, int[] depth, int[] dist) {
final int lca = getLCA(u, v, jump, depth);
return dist[u] + dist[v] - 2 * dist[lca];
}
} // code provided by PROGIEZ
3553. Minimum Weighted Subgraph With the Required Paths II LeetCode Solution in Python
class Solution:
# Similar to 2846. Minimum Edge Weight Equilibrium Queries in a Tree
def minimumWeight(
self,
edges: list[list[int]],
queries: list[list[int]]
) -> list[int]:
n = len(edges) + 1
m = math.ceil(math.log2(n))
graph = [[] for _ in range(n)]
jump = [[0] * m for _ in range(n)] # jump[i][j] := the 2^j-th ancestor of i
depth = [0] * n # depth[i] := the depth of i
dist = [0] * n # dist[i] := the distance from root to i
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
self._dfs(graph, 0, -1, jump, depth, dist)
for j in range(1, m):
for i in range(n):
jump[i][j] = jump[jump[i][j - 1]][j - 1]
return [(self._distance(src1, src2, jump, depth, dist) +
self._distance(src1, dest, jump, depth, dist) +
self._distance(src2, dest, jump, depth, dist)) // 2
for src1, src2, dest in queries]
def _dfs(
self,
graph: list[list[tuple[int, int]]],
u: int,
prev: int,
jump: list[list[int]],
depth: list[int],
dist: list[int]
) -> None:
for v, w in graph[u]:
if v == prev:
continue
jump[v][0] = u
depth[v] = depth[u] + 1
dist[v] = dist[u] + w
self._dfs(graph, v, u, jump, depth, dist)
def _getLCA(
self,
u: int,
v: int,
jump: list[list[int]],
depth: list[int]
) -> int:
"""Returns the lca(u, v) by binary jump."""
# v is always deeper than u.
if depth[u] > depth[v]:
return self._getLCA(v, u, jump, depth)
# Jump v to the same height of u.
for j in range(len(jump[0])):
if depth[v] - depth[u] >> j & 1:
v = jump[v][j]
if u == v:
return u
# Jump u and v to the node right below the lca.
for j in range(len(jump[0]) - 1, -1, -1):
if jump[u][j] != jump[v][j]:
u = jump[u][j]
v = jump[v][j]
return jump[u][0]
def _distance(
self,
u: int,
v: int,
jump: list[list[int]],
depth: list[int],
dist: list[int]
) -> int:
"""Returns the distance between u and v."""
lca = self._getLCA(u, v, jump, depth)
return dist[u] + dist[v] - 2 * dist[lca] # code by PROGIEZ
