3553. Minimum Weighted Subgraph With the Required Paths II Hard

1/**
2 * [3553] Minimum Weighted Subgraph With the Required Paths II
3 *
4 * You are given an undirected weighted tree with <code data-end="51" data-start="48">n nodes, numbered from <code data-end="75" data-start="72">0 to <code data-end="86" data-start="79">n - 1. It is represented by a 2D integer array <code data-end="129" data-start="122">edges of length <code data-end="147" data-start="140">n - 1, where <code data-end="185" data-start="160">edges[i] = [ui, vi, wi] indicates that there is an edge between nodes <code data-end="236" data-start="232">ui and <code data-end="245" data-start="241">vi with weight <code data-end="262" data-start="258">wi.​
5 * Additionally, you are given a 2D integer array <code data-end="56" data-start="47">queries, where <code data-end="105" data-start="69">queries[j] = [src1j, src2j, destj].
6 * Return an array <code data-end="24" data-start="16">answer of length equal to <code data-end="60" data-start="44">queries.length, where <code data-end="79" data-start="68">answer[j] is the minimum total weight of a subtree such that it is possible to reach <code data-end="174" data-start="167">destj from both <code data-end="192" data-start="185">src1j and <code data-end="204" data-start="197">src2j using edges in this subtree.
7 * A <strong data-end="2287" data-start="2276">subtree here is any connected subset of nodes and edges of the original tree forming a valid tree.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">edges = [[0,1,2],[1,2,3],[1,3,5],[1,4,4],[2,5,6]], queries = [[2,3,4],[0,2,5]]</span>
12 * Output: <span class="example-io">[12,11]</span>
13 * Explanation:
14 * The blue edges represent one of the subtrees that yield the optimal answer.
15 * <img alt="" src="https://assets.leetcode.com/uploads/2025/04/02/tree1-4.jpg" style="width: 531px; height: 322px;" />
16 * 
17 * 	<li data-end="118" data-start="0">
18 * 	<p data-end="118" data-start="2">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.
19 * 	
20 * 	<li data-end="235" data-start="119">
21 * 	<p data-end="235" data-start="121">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.
22 * 	
23 * </div>
24 * <strong class="example">Example 2:
25 * <div class="example-block">
26 * Input: <span class="example-io">edges = [[1,0,8],[0,2,7]], queries = [[0,1,2]]</span>
27 * Output: <span class="example-io">[15]</span>
28 * Explanation:
29 * <img alt="" src="https://assets.leetcode.com/uploads/2025/04/02/tree1-5.jpg" style="width: 270px; height: 80px;" />
30 * 
31 * 	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.
32 * </div>
33 *  
34 * Constraints:
35 * 
36 * 	<li data-end="36" data-start="20">3 <= n <= 10^5
37 * 	<li data-end="62" data-start="39">edges.length == n - 1
38 * 	<li data-end="87" data-start="65">edges[i].length == 3
39 * 	<li data-end="107" data-start="90">0 <= ui, vi < n
40 * 	<li data-end="127" data-start="110">1 <= wi <= 10^4
41 * 	<li data-end="159" data-start="130">1 <= queries.length <= 10^5
42 * 	<li data-end="186" data-start="162">queries[j].length == 3
43 * 	<li data-end="219" data-start="189">0 <= src1j, src2j, destj < n
44 * 	src1j, src2j, and destj are pairwise distinct.
45 * 	The input is generated such that edges represents a valid tree.
46 * 
47 */
48pub struct Solution {}
49
50// problem: https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths-ii/
51// discuss: https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths-ii/discuss/?currentPage=1&orderBy=most_votes&query=
52
53// submission codes start here
54
55impl Solution {
56    pub fn minimum_weight(edges: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
57        vec![]
58    }
59}
60
61// submission codes end
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    #[test]
68    fn test_3553() {
69    }
70}
71