Heavy-Light Decomposition

You are given a rooted tree with N nodes. The nodes are numbered from 1 to N, and the root is the node numbered 1. For each node X which is not a leaf, you must choose a node Y which is a child of X and mark the edge between X and Y as heavy (red in the picture below). Once this has been done, we calculate the cost of each path from the root to a leaf. For this, we decompose the path into segment