I'm trying to understand Heavy-Light decomposition method for answering LCA queries , but stuck with it. I'm not able to understand the concept of exactly why you needed "vertex-disjoint" and "edge-disjoint" paths. And as I see in some problems we pre-process "edge-disjoint" paths with segment trees. Why we would do that?
Can some help in rephrasing the whole idea step-by-step? I'm following problem E from http://felix-halim.net/story/icpc10/problems.pdf . Any help would be appreciated.
Check this link
Partitioning the tree into disjoint paths will help you quickly jump from one node to the root. Take a look at this picture.
This tree is partitioned into 3 chains and each chain is a segment tree. Suppose that you want to query the data on the path from node a to the root. First, we get the data from a to b in the segment tree of the green chain. Then jump to the red chain and get the data from c to the root. It can be proved that the number of time that we jump from chain to chain is at most lgN
You can find proof and applications here