Explanation of Heavy light decomposition
I am taking this from http://wcipeg.com/wiki/Heavy-light_decomposition

Essentially the decomposition tells you which, if any, subtrees at a node N take up more than half the weight of the tree rooted at N.  Such a subtree gets an edge coloured with the word "Heavy" the rest get coloured "Light".  Note that there can be at most one heavy subtree at any given node.

Here is an implementation in Haskell.

module HLDecom where

{- |
  This data type has data in the leaves and nodes 
  that collect a list of subtrees each of which is 
  paired with b-type data.  The b should be thought
  of as information on the edge connecting the node
  to the subtree.
-}
data Tree a b = Leaf a | Node [(b,Tree a b)]

data Color = Heavy | Light

size :: Tree a b -&gt; Integer
size (Leaf x) = 1
size (Node ns) = 1 + sum (map (\(a,b) -&gt; size b) ns)

{- |
  The Heavy-Light decomposition of a tree is a 
  colouring of the tree's edges with 
  either Heavy or Light.  

  If the size of a subtree at a node is more 
  than half the size of the tree at the node, 
  then the edge connecting the node to that 
  subtree is heavy otherwise it is light.

  It should be obvious that at any given node,
  there can only be one such heavy subtree 
  (there can only be one subtree that 
  has &gt; 1/2 the weight), and further we can find 
  this subtree by finding the maximum size subtree.  
  If this size is more than half the size of 
  the whole tree, then it is colored Heavy.

  The implementation below could certainly be 
  improved for efficiency; however, the focus 
  on being direct and clear.
-}
--hlDecomp :: Tree a b -&gt; Tree a Color
hlDecomp (Leaf x) = (Leaf x) 
hlDecomp (Node ns) = 
  let
    sizeOfNode = size (Node ns)
    heavyLight = map (\(b,tree) -&gt;
       if size tree &gt; 
          sizeOfNode `div` 2 
          then (Heavy,tree) 
          else (Light,tree)) ns
  in
    Node heavyLight