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 < |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 < |a|}{1-\frac{a_i}{a_{i + 1} - 1}} \leq \sum_{i = 1}^{i < |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 < |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)$.↵
↵
###uUsages↵
↵
remain to the reader
↵
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 < |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 < |a|}{1-\frac{a_i}{a_{i + 1} - 1}} \leq \sum_{i = 1}^{i < |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 < |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)$.↵
↵
###
↵
remain to the reader
