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.
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.
You are also given a 2D integer array queries of length q, where each queries[i] is either:
Return an integer array answer, where answer[i] is the shortest path distance from node 1 to x for the ith 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]
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
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.