3515. Shortest Path in a Weighted Tree

Hard

50 Points

Array

Tree

Depth-First Search

Binary Indexed Tree

Segment 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 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].

Examples

Example 1

Input: n = 2, edges = [[1,2,7]], queries = [[2,2],[1,1,2,4],[2,2]] Output: [7,4] Explanation:

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] Explanation:

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] Explanation:

Constraints

1 <= n <= 105
edges.length == n - 1
edges[i] == [ui, vi, wi]
1 <= ui, vi <= n
1 <= wi <= 104
The input is generated such that edges represents a valid tree.
1 <= queries.length == q <= 105
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' <= 104
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' <= 104