Skip to content

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 Problem

Shortest 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.