Path Maximum with Updates
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 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 campsiteutox.[2, u, v]— report the maximum score on the route fromutov, both ends included (u = vis allowed).
Return the answers to the type-2 queries in order.
Examples
| n | edges | values | queries | result |
|---|---|---|---|---|
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
-
n edges.lengthn,edges[i] = [u, v],n; the trails form a tree.-
values[i],x -
queries.length, with at least one type-2 query.
Expected complexity
- Time
- O(N + Q log^2 N)
- Space
- O(N)
Examples
| n | edges | values | queries | Expected |
|---|---|---|---|---|
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 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 (). Use iterative DFS since the tree can be very deep. Walking the path step by step is per query and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 604 ms | estimated |
| C++ (GCC, gnu++23) | 604 ms | derived |
| Python 3.13 | 3778 ms | derived |
| Java 25 | 2768 ms | derived |
| Kotlin 2.4 (JVM) | 2208 ms | estimated |
| C# 14 (.NET 10) | 2208 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |