How should I practice Sum Dynamic Weighted Tree Distances?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Juspay online assessment problems in FastPrep.

Is Sum Dynamic Weighted Tree Distances associated with Juspay?

FastPrep tags this as a Juspay online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Sum Dynamic Weighted Tree Distances

Learn this problem

● Hard

JuspayNEW GRADOA

Problem statement

You are given a connected, undirected tree with n vertices numbered from 1 to n. Each row [u, v, weight] in edges describes one weighted edge.

Process every row in queries from left to right:

[1, u, v, newWeight] replaces the current weight of the existing undirected edge between u and v with newWeight.
[2, u, v] asks for the current shortest-path distance between u and v. Because the graph is a tree, this is the sum of the current edge weights on their unique path.

Return the sum of the answers to all type 2 queries. If there are no type 2 queries, return 0.

Function

sumTreeQueryDistances(n: int, edges: int[][], queries: int[][]) → long

Examples

Example 1

n = 5edges = [[1,2,4],[1,3,2],[3,4,7],[3,5,1]]queries = [[2,2,4],[1,1,3,5],[2,2,4],[2,4,5]]return = 37

The first distance is 4 + 2 + 7 = 13. Replacing the weight of edge (1, 3) by 5 makes the next distance 4 + 5 + 7 = 16. The last distance, from 4 to 5, is 7 + 1 = 8. Their sum is 13 + 16 + 8 = 37.

Example 2

n = 3edges = [[1,2,1000000000],[2,3,1000000000]]queries = [[2,1,3],[1,2,1,3],[2,1,3],[2,2,2]]return = 3000000003

The first path has length 2,000,000,000. The update names edge (1, 2) in reverse order and replaces its weight by 3, so the next path has length 1,000,000,003. The distance from vertex 2 to itself is 0. The total is 3,000,000,003.

Example 3

n = 1edges = []queries = [[2,1,1]]return = 0

A path from the only vertex to itself contains no edges, so its distance and the returned sum are both 0.

Constraints

1 <= n <= 2 * 10^5.
edges.length = n - 1.
Every row in edges is [u, v, weight], where 1 <= u, v <= n and 1 <= weight <= 10^9.
edges forms a connected, undirected tree.
1 <= queries.length <= 2 * 10^5.
Every query is either [1, u, v, newWeight] or [2, u, v].
Every type 1 query names an existing tree edge and satisfies 1 <= newWeight <= 10^9.
Every type 2 query satisfies 1 <= u, v <= n.
The returned sum fits in a signed 64-bit integer.