3515. Shortest Path in a Weighted Tree Hard

1/**
2 * [3515] Shortest Path in a Weighted Tree
3 *
4 * You are given an integer n and an undirected, weighted tree rooted at node 1 with n nodes numbered from 1 to n. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi, wi] indicates an undirected edge from node ui to vi with weight wi.
5 * You are also given a 2D integer array queries of length q, where each queries[i] is either:
6 * 
7 * 	[1, u, v, w'] – Update the weight of the edge between nodes u and v to w', where (u, v) is guaranteed to be an edge present in edges.
8 * 	[2, x] – Compute the shortest path distance from the root node 1 to node x.
9 * 
10 * Return an integer array answer, where answer[i] is the shortest path distance from node 1 to x for the i^th query of [2, x].
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">n = 2, edges = [[1,2,7]], queries = [[2,2],[1,1,2,4],[2,2]]</span>
15 * Output: <span class="example-io">[7,4]</span>
16 * Explanation:
17 * <img src="https://assets.leetcode.com/uploads/2025/03/13/screenshot-2025-03-13-at-133524.png" style="width: 200px; height: 75px;" />
18 * 
19 * 	Query [2,2]: The shortest path from root node 1 to node 2 is 7.
20 * 	Query [1,1,2,4]: The weight of edge (1,2) changes from 7 to 4.
21 * 	Query [2,2]: The shortest path from root node 1 to node 2 is 4.
22 * </div>
23 * <strong class="example">Example 2:
24 * <div class="example-block">
25 * Input: <span class="example-io">n = 3, edges = [[1,2,2],[1,3,4]], queries = [[2,1],[2,3],[1,1,3,7],[2,2],[2,3]]</span>
26 * Output: <span class="example-io">[0,4,2,7]</span>
27 * Explanation:
28 * <img src="https://assets.leetcode.com/uploads/2025/03/13/screenshot-2025-03-13-at-132247.png" style="width: 180px; height: 141px;" />
29 * 
30 * 	Query [2,1]: The shortest path from root node 1 to node 1 is 0.
31 * 	Query [2,3]: The shortest path from root node 1 to node 3 is 4.
32 * 	Query [1,1,3,7]: The weight of edge (1,3) changes from 4 to 7.
33 * 	Query [2,2]: The shortest path from root node 1 to node 2 is 2.
34 * 	Query [2,3]: The shortest path from root node 1 to node 3 is 7.
35 * </div>
36 * <strong class="example">Example 3:
37 * <div class="example-block">
38 * Input: <span class="example-io">n = 4, edges = [[1,2,2],[2,3,1],[3,4,5]], queries = [[2,4],[2,3],[1,2,3,3],[2,2],[2,3]]</span>
39 * Output: [8,3,2,5]
40 * Explanation:
41 * <img src="https://assets.leetcode.com/uploads/2025/03/13/screenshot-2025-03-13-at-133306.png" style="width: 400px; height: 85px;" />
42 * 
43 * 	Query [2,4]: The shortest path from root node 1 to node 4 consists of edges (1,2), (2,3), and (3,4) with weights 2 + 1 + 5 = 8.
44 * 	Query [2,3]: The shortest path from root node 1 to node 3 consists of edges (1,2) and (2,3) with weights 2 + 1 = 3.
45 * 	Query [1,2,3,3]: The weight of edge (2,3) changes from 1 to 3.
46 * 	Query [2,2]: The shortest path from root node 1 to node 2 is 2.
47 * 	Query [2,3]: The shortest path from root node 1 to node 3 consists of edges (1,2) and (2,3) with updated weights 2 + 3 = 5.
48 * </div>
49 *  
50 * Constraints:
51 * 
52 * 	1 <= n <= 10^5
53 * 	edges.length == n - 1
54 * 	edges[i] == [ui, vi, wi]
55 * 	1 <= ui, vi <= n
56 * 	1 <= wi <= 10^4
57 * 	The input is generated such that edges represents a valid tree.
58 * 	1 <= queries.length == q <= 10^5
59 * 	queries[i].length == 2 or 4
60 * 	
61 * 		queries[i] == [1, u, v, w'] or,
62 * 		queries[i] == [2, x]
63 * 		1 <= u, v, x <= n
64 * 		<code data-end="37" data-start="29">(u, v) is always an edge from <code data-end="74" data-start="67">edges.
65 * 		1 <= w' <= 10^4
66 * 	
67 * 	
68 * 
69 */
70pub struct Solution {}
71
72// problem: https://leetcode.com/problems/shortest-path-in-a-weighted-tree/
73// discuss: https://leetcode.com/problems/shortest-path-in-a-weighted-tree/discuss/?currentPage=1&orderBy=most_votes&query=
74
75// submission codes start here
76
77impl Solution {
78    pub fn tree_queries(n: i32, edges: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
79        vec![]
80    }
81}
82
83// submission codes end
84
85#[cfg(test)]
86mod tests {
87    use super::*;
88
89    #[test]
90    fn test_3515() {
91    }
92}
93