How do you usually build HLD?
Usually we calculate $$$sz_v$$$ — size of subtree of $$$v$$$. Then from $$$v$$$ we go to $$$u$$$ with largest $$$sz_u$$$ ($$$u$$$ is child of $$$v$$$). And this is still good way, but today I want to show you something different.
What if from $$$v$$$ we go to the random vertex $$$u$$$ in the whole subtree of $$$v$$$. It is the same as choosing to go to the $$$u$$$ ($$$u$$$ is child of $$$v$$$) with probability $$$\frac{sz_u}{sz_v - 1}$$$, so the probability of edge $$$v, u$$$ to be heavy is $$$\frac{sz_u}{sz_v - 1}$$$. Intuitively we should go the largest subtree.
Proof
Let's proof it works well. For vertex $$$v$$$ the expected value number of light edges on the way to root is $$$\sum_{i = 1}^{i \lt |u|}{1-\frac{sz_{u_i}}{sz_{u_{i + 1}} - 1}}$$$, where $$$u$$$ is vertexes on way from $$$v$$$ to root. Let $$$a_i$$$ be $$$sz_{u_i}$$$. Then $$$a$$$ is an increasing array and we know that $$$a_{h_v}$$$ equals to the size of the whole tree. $$$\sum_{i = 1}^{i \lt |a|}{1-\frac{a_i}{a_{i + 1} - 1}} \leq \sum_{i = 1}^{i \lt |a|}{\frac{a_{i + 1} - a_i}{a_{i + 1}}}$$$.
$$$\frac{a_{i+1} - a_i}{a_{i+1}} \le \int_{a_i}^{a_{i+1}} \frac{1}{x} \, dx = \ln(a_{i+1}) - \ln(a_i)$$$
$$$\sum_{i = 1}^{i \lt |a|}{1-\frac{a_i}{a_{i + 1} - 1}} \leq ln(a_{|a|})$$$.
So we have expected value number of light edges on the way is less than $$$ln(n)$$$.
Usages
remain to the reader
