The Path Query Problem

You are given a tree with $n$ nodes. Each node has a value val[i]. You need to handle two operations: query the maximum value on the path from node $u$ to node $v$, and update the value of node $i$ to $x$. If you walk the path for each query, visiting each node along the way, you get $O(n)$ per query.

With $q = 100000$ queries and $n = 100000$ nodes, that is $10^{10}$ operations, which times out. You need a faster approach that does not visit every node on the path. This is where Heavy-Light Decomposition comes in.

Space complexity is $O(n)$ for the data structures used.