Practice Shortest Path in a Weighted Tree
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Hard#3515
LeetCode ProblemShortest Path in a Weighted Tree
Problem Statement
The weighted undirected tree has nodes 1 through n, root 1, and edges [u, v, weight]. Process queries in order. A query [1, u, v, newWeight] changes the weight of the specified existing edge; [2, x] asks for the current path distance from node 1 to x. Return the answers to type-2 queries in order.
Source: Shortest Path in a Weighted Tree on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
Input
n = 2, edges = [[1,2,7]], queries = [[2,2],[1,1,2,4],[2,2]]
Output
[7,4]
# Example 2
Input
n = 3, edges = [[1,2,2],[1,3,4]], queries = [[2,1],[2,3],[1,1,3,7],[2,2],[2,3]]
Output
[0,4,2,7]
# Example 3
Input
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]]
Output
[8,3,2,5]
Constraints
1 <= n <= 10^5
edges.length == n - 1
edges[i] == [ui, vi, wi]
1 <= ui, vi <= n
1 <= wi <= 10^4
The input is generated such that edges represents a valid tree.
1 <= queries.length == q <= 10^5
queries[i].length == 2 or 4
queries[i] == [1, u, v, w'] or,
queries[i] == [2, x]
1 <= u, v, x <= n
(u, v) is always an edge from edges.
1 <= w' <= 10^4
queries[i] == [1, u, v, w'] or,
queries[i] == [2, x]
1 <= u, v, x <= n
(u, v) is always an edge from edges.
1 <= w' <= 10^4
Related LeetCode Problems
Practice more problems similar to Shortest Path in a Weighted Tree.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.