deam0n's blog

Help needed for Heavy-Light decomposition.
By deam0n, 11 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Check this link

→ Reply
»
11 years ago, # |
← Rev. 5   Vote: I like it +4 Vote: I do not like it

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

→ Reply