Maximum Value on Tree Paths - Adobe Hackathon 2026

Problem Preview

"You are given a static tree with n nodes. Each node has an integer value. You need to answer q queries. For each query (u, v), find the maximum node value on the unique path from node u to node v, including both endpoints. There are no updates to the tree. Because the number of queries can be very large, your solution should efficiently answer path queries. Input Format n q a1 a2 ... an u1 v1 u2 v2 ... uq vq n = number of nodes q = number of queries ai = value of node i Next n-1 lines contain the edges: u v Next q lines contain queries (u, v). Constraints 1 ≤ n ≤ 2 × 10^5 1 ≤ q ≤ 2 × 10^5 1 ≤ ai ≤ 10^9 1 ≤ u, v ≤ n The tree contains exactly n-1 edges. Output For every query, print the maximum value on the path. Test Case 1 5 3 5 2 9 1 7 1 2 1 3 2 4 2 5 1 4 4 5 3 4 Tree: 1(5) / \ 2(2) 3(9) / \ 4(1) 5(7) Queries: 1 → 4: values 5, 2, 1 → 5 4 → 5: values 1, 2, 7 → 7 3 → 4: values 9, 5, 2, 1 → 9 Output: 5 7 9 Expected Approach Heavy-Light Decomposition + Segment Tree"