Operations We Need

A Link-Cut tree supports:

$1.$ link(u, v): Make $u$ a child of $v$. (Trees must be in different components.)

$2.$ cut(u): Remove edge from $u$ to its parent.

$3.$ findRoot(u): Find root of $u$'s tree.

$4.$ pathQuery(u, v): Query aggregate (sum/min/max) on path from $u$ to $v$.

$5.$ pathUpdate(u, v, val): Update all nodes on path from $u$ to $v$.

$6.$ lca(u, v): Find lowest common ancestor.

All operations run in $O(\log n)$ amortized time. Space: $O(n)$.