Intro

You can answer subtree queries in $O(\log n)$ with Euler tours and segment trees.

But what about path queries? Given two nodes $u$ and $v$, find the maximum value on the path between them. The naive approach visits every node on the path. In a line graph with $n$ nodes, paths can have length $n-1$, making each query $O(n)$.

With $q$ queries, that is $O(nq)$ total. In this section, I'll show you Heavy-Light Decomposition, a technique that splits any tree into $O(\log n)$ chains. This turns path queries into $O(\log n)$ range queries on a segment tree, giving $O(q \log^2 n)$ total time.