Heavy-Light Decomposition

Heavy edges form chains · each chain maps to a contiguous array slice · a path query splits into O(log N) chain segments climbing to the LCA · each segment is one segment-tree range query → O(log² N)

Tree Preset

Path Query

Legend

Heavy edge (chain)
Light edge
Query endpoints u, v
Current chain segment
LCA (split point)
Already-queried nodes
Pick a preset, then u and v, and press Step to watch the path query climb chain by chain to the LCA. Toggle edge mode to see the LCA skipped (edge-weight variant).

Step Log

Step log will appear here.

Tree — heavy chains colored, light edges thin/gray

Linearized array (DFS heavy-child-first) — chains are contiguous

Segment tree over base[pos] — highlighted range = current chain segment

How to read this

Heavy edges connect each node to its largest-subtree child. Following only heavy edges partitions the tree into vertical chains. The heavy-child-first DFS lays every chain into a contiguous block of array positions — see how each colored chain above maps to one unbroken slice of the linearized array and the segment-tree band.

A path(u, v) query repeatedly takes the endpoint whose chain head is deeper, answers a single segment-tree range query for that endpoint's slice [pos(head)..pos(node)], then jumps over one light edge to parent(head). Because every light edge at least halves the subtree, a path crosses at most 2⌈log₂N⌉ light edges, so the loop runs O(log N) times — each iteration an O(log N) segment-tree query → O(log² N) overall.

Try the Path preset: it is one giant chain, so a path query is a single range query (no light edges). The Star preset is the opposite — every leaf is its own chain, so a leaf-to-leaf path touches three tiny chains. The Balanced and Caterpillar presets push the chain count toward the log N worst case. The metric under the status box reports the realized chain count against the worst-case bound.