1106. Path Maximum With Updates

Hard7.5 points estimatedTree Segment Tree Depth-First Search Design 3 hints

A telecom backbone consists of n relay stations numbered 0 to n - 1, joined by n - 1 cables so that exactly one route exists between any two stations (a tree). Station i currently reports a noise level values[i], which may be negative.

Implement the class PathMax:

PathMax(int n, int[][] edges, int[] values) builds the structure; each edges[i] = [a, b] is a two-way cable.
void update(int node, int value) sets the noise level of station node to value.
int pathMax(int u, int v) returns the highest current noise level among all stations on the route from u to v, both ends included.

Example 1

Input:: operations = ["PathMax","pathMax","update","pathMax","pathMax","update","pathMax"]arguments = [[5,[[0,1],[1,2],[1,3],[3,4]],[4,9,2,7,5]],[2,4],[1,1],[2,4],[4,4],[4,10],[0,4]]
Output:: [null,9,null,7,5,null,10]
Explanation:: The route 2-1-3-4 has noise 2, 9, 7, 5 (max 9); after station 1 drops to 1 the same route gives 7; a single station gives its own level 5; after station 4 rises to 10 the route 0-1-3-4 gives 10.

Example 2

Input:: operations = ["PathMax","pathMax","update","pathMax","pathMax"]arguments = [[3,[[0,1],[1,2]],[-5,-2,-9]],[0,2],[1,-20],[2,0],[1,1]]
Output:: [null,-2,null,-5,-20]
Explanation:: Noise levels may be negative: the best on route 0-1-2 is -2; after station 1 drops to -20 the best on the route is -5; asking about station 1 alone returns its new level, -20.

Example 3

Input:: operations = ["PathMax","pathMax","update","pathMax"]arguments = [[1,[],[7]],[0,0],[0,-3],[0,0]]
Output:: [null,7,null,-3]
Explanation:: A single station forms the whole tree, so pathMax returns its own level before and after the update.

Constraints

1 ≤ n ≤ 100000

edges.length == n - 1; the cables form a tree

-10⁹ ≤ values[i], value ≤ 10⁹

At most 100000 calls in total to update and pathMax; 0 ≤ node, u, v < n (u may equal v)

How this problem is judged

Answers: Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input: Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time: O(log^2 n) per operation
Space: O(n)

What the author was aiming for. Your own solution is not measured against it.

Were you asked this in an interview? Say where, anonymously.

CodeStarter code

Loading the editor…

operations =arguments =

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.