Heavy child
For each node, heavy child = child with largest subtree. Others are light.
Advertisement
Chain formation
Follow heavy edges → chain. Root of each chain is either the tree root or the top of a light edge.
Advertisement
Path query
To query path u→v: repeatedly jump v to top-of-chain, apply segment tree query on chain range, jump above chain root. O(log² N) queries.
Applications
Path sum queries. Path max. LCA queries. Subtree queries via Euler tour indexing.