Shortest Path in a Weighted Tree
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 node vi with weight wi.
You are also given a 2D integer array queries of length q, where each queries[i] is either:
[1, u, v, w']– Update the weight of the edge between nodesuandvtow', where(u, v)is guaranteed to be an edge present inedges.[2, x]– Compute the shortest path distance from the root node1to nodex.
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].
Example 1
Input
n = 2, edges = [[1,2,7]], queries = [[2,2],[1,1,2,4],[2,2]]Output
[7,4]The distance from node 1 to node 2 is initially 7, then after updating edge (1,2) to weight 4, the distance becomes 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]The reported distances for query nodes are 0 for node 1, 4 for node 3, 2 for node 2, and 7 for node 3 after updating edge (1,3).
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