You are given a tree with nodes. Each node has a value val[i]. You need to handle two operations: query the maximum value on the path from node to node , and update the value of node to . If you walk the path for each query, visiting each node along the way, you get per query.
With queries and nodes, that is 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 for the data structures used.