How to compute the loss and backprop of word2vec skip-gram using hierarchical softmax?

So we are calculating the loss

$$J(\theta) = -\frac{1}{T}\sum_{t=1}^T\sum_{-m \leq j \leq m} \log P(w_{t+j}|w_t;\theta)$$

and to do this we need to calculate

$$P(o|c) = \frac{\exp(u_o^Tv_c)}{\sum \exp(u_w^Tv_c)},$$

which is computationally inefficient. To solve this we could use the hierarchical softmax and construct a tree based on word frequency. However, I am having trouble on how we could get the probability based on the word frequency. And what exactly is the backprop step if using hierarchical softmax?