heavy light decomposition

After doing a lot of research i cant find any good content on this topic(heavy light decomposition)
however i found some good link i still have some doubt after reading this topic please help

http://blog.anudeep2011.com/heavy-light-decomposition/#comment-654

1)i cant understand the implementation of code(i mean i need a driver code in main)

2)how the code for query works

please help

thankyou

1 Like

Brother, this answer presents a technique called Heavy Light Decomposition of a tree.

Basic Idea

Consider a node x. Let x have children u and v.

The edge x-u is called heavy if size(u) > 1/2 * size(x), otherwise it is called a light edge.

If a node has many children, then it is easy to note that at the most there can only be one heavy edge. It can be shown as follows:

Let the node be z and its children be u1,u2,….

Now,let the edge z-u1 and z-u2 be the heavy edges.

=> size(u1) > 1/2 * size(z) and size(u2) > 1/2 * size(z)
=> size(u1) + size(u2) > size(z)

which is a contradiction as size(u1) + size(u2) + size(u3) + … <= size(z)

Hence, there can at the most only one heavy edge connecting a node to its children.

So, if we look at a node, there can be at the most two heavy edges it may be connected to. One with its parent and the other with one of its children.

Light Edges

Considering the light edges, suppose if the edge x-y is light. Therefore, size(y) <= 1/2 * size(x), which means whenever we follow a light edge, the size of the tree is atleast halved. As a result, the number of light edges is O(lg n).

Building the Heavy Light Decomposition

The heavy light decomposition can be built using dfs.Pseudo Code for the same is given below.

Ancestors and Lowest Common Ancestor

One of the major applications of the heavy light decomposition is the Lowest Common Ancestor queries.

Suppose if we want to find the whether a node is and ancestor of another node. This can be easily done using the time_in and time_out arrays computed in the above DFS code.time_in entry for a node gives the time when the node is first discovered and the time_out entry determines the time when all of its children have been explored. Let the nodes be x and y. The following condition checks if x is an ancestor of y:

if time_in[x] < time_in[y] and time_out[x] > time_out[y]
then print x is an ancestor of y

If we consider a Heavy Light Decomposition of a tree, then there will be chains heavy edges and then we will have the light edges. We can completely skip the heavy edges. Below is the pseudocode for the LCA problems which uses the above described ideas.

Driver function can be removed by replacing it with input method like scanf & printing the answer by placing the function in printf.

5 Likes

just a minor change in anudeep’s implementation on heavy light decomp: he calls an edge heavy if it goes to the child with the biggest amount of nodes in its subtree, not only the child with > 1/2 nodes.

You can find here a clean code of HLD which is the solution of SPOJ- QTREE ( Link )

1 Like