Problem - Path Queries

Given a tree with $n$ nodes, each with a value. Process $q$ queries:

$1.$ Update: change the value of node $u$ to $v$

$2.$ Query: find the maximum value on the path from $u$ to $v$

Constraints: $n, q \leq 2 \cdot 10^5$. You're solving the classic HLD problem. The tree structure prevents using standard segment trees directly. HLD breaks the tree into chains, each handled by a segment tree. Before reading the solution, think about why sqrt decomposition wouldn't work well here.