Funcia
Lv.4heavy-light-decompositionsegment-treetree

Path Maximum with Updates

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

n campsites (0..n-1) are joined by n-1 trails so that every pair has exactly one route (a tree); edges[i] = [u, v] is a trail and campsite i has scenery score values[i]. Process queries in order:

  • [1, u, x] — set the score of campsite u to x.
  • [2, u, v] — report the maximum score on the route from u to v, both ends included (u = v is allowed).

Return the answers to the type-2 queries in order.

Examples

nedgesvaluesqueriesresult
5[[0, 1], [1, 2], [1, 3], [3, 4]][3, 1, 4, 1, 5][[2, 2, 4], [1, 4, 0], [2, 2, 4], [2, 0, 1], [1, 0, 9], [2, 3, 3]][5, 4, 3, 1]
3[[2, 1], [1, 0]][-5, -7, -6][[2, 0, 2], [2, 1, 1], [1, 0, -8], [2, 2, 0]][-5, -7, -6]

Example 1 — route 2 → 1 → 3 → 4 has scores 4, 1, 1, 5; after campsite 4 drops to 0 its maximum is 4.

Example 2 — scores may be negative.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(n: int, edges: int[][], values: int[], queries: int[][]) → int[]

Constraints

  • 1≤1 \le n ≤200,000\le 200{,}000
  • edges.length == n −1- 1, edges[i] = [u, v], 0≤u,v<0 \le u, v < n; the trails form a tree.
  • −109≤-10^9 \le values[i], x ≤109\le 10^9
  • 1≤1 \le queries.length ≤200,000\le 200{,}000, with at least one type-2 query.

Expected complexity

Time
O(N + Q log^2 N)
Space
O(N)

Examples

nedgesvaluesqueriesExpected
5[[0,1],[1,2],[1,3],[3,4]][3,1,4,1,5][[2,2,4],[1,4,0],[2,2,4],[2,0,1],[1,0,9],[2,3,3]][5,4,3,1]
3[[2,1],[1,0]][-5,-7,-6][[2,0,2],[2,1,1],[1,0,-8],[2,2,0]][-5,-7,-6]

Hint

Hint

Use heavy-light decomposition: root the tree, call the edge to the child with the largest subtree "heavy", and number the vertices so that each heavy chain is a contiguous range; any path then splits into O(log⁡n)O(\log n) chain segments. Store the scores in a max segment tree over that numbering. Updates are point updates; a path query repeatedly takes the range from the deeper chain head to the current vertex and jumps to the head's parent until both ends share a chain (O(log⁡2n)O(\log^2 n)). Use iterative DFS since the tree can be very deep. Walking the path step by step is O(n)O(n) per query and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)604 msestimated
C++ (GCC, gnu++23)604 msderived
Python 3.133778 msderived
Java 252768 msderived
Kotlin 2.4 (JVM)2208 msestimated
C# 14 (.NET 10)2208 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.