Ridge Path Maximum Problem

Ridge Path Maximum Problem — ExecCode Hard DSA Practice

Solve the Ridge Path Maximum problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Each cabin on a ridge tree stores a snow-depth reading. Inspectors ask for the maximum reading on the unique path between two cabins, and sometimes overwrite a cabin's reading. Heavy-light decomposition turns each path into O(log n) ranges on a segment tree. Link-cut trees would also work if the ridge itself were being rewired. Process queries in order. Type 0 u v appends the maximum value on the path from u to v. Type 1 u x sets node u to x and appends nothing. Return the appended maxima. You are given: n — nodes edges — tree edges values — initial readings queries — [type, ...] Return maxima from type-0 queries. If u = v the answer is that node's current value.

Examples

Input {'n': 4, 'edges': [[0, 1], [0, 2], [2, 3]], 'values': [1, 8, 3, 2], 'queries': [[0, 1, 3], [1, 2, 9], [0, 1, 3]]}; Output [8, 9]. Input {'n': 1, 'edges': [], 'values': [4], 'queries': [[0, 0, 0]]}; Output [4]. Input {'n': 3, 'edges': [[0, 1], [0, 2]], 'values': [5, 5, 7], 'queries': [[0, 1, 2]]}; Output [7]

Constraints

Mixed updates and path maxima Path endpoints may be equal

Practice Ridge Path Maximum free on ExecCode. Browse DSA problems, topic map, and placement guides.