You can answer subtree queries in with Euler tours and segment trees.
But what about path queries? Given two nodes and , find the maximum value on the path between them. The naive approach visits every node on the path. In a line graph with nodes, paths can have length , making each query .
With queries, that is total. In this section, I'll show you Heavy-Light Decomposition, a technique that splits any tree into chains. This turns path queries into range queries on a segment tree, giving total time.
