Uniformly random iteration of subtrees

Question

I want to iterate through the first $k$ elements of a randomly ordered list containing all subtrees for a given tree. The definition of subtrees that I'm using is: "A subtree of $T$ is a subgraph of $T$ that is also a tree". For example, a tree $A(B(D, E, F), C(G, H))$ should have 62 subtrees if my math is correct.

The amount of subtrees can be calculated as follows. Let us denote by $R(T)$ the number of subtrees of $T$ rooted at $T$. If $T$ is a leaf then $R(T) = 1$, and if tree has children $T_1,\ldots,T_\ell$ then $$ R(T) = \prod_{i=1}^\ell (R(T_i) + 1). $$ Finally, the number of subtrees of $T$ is $\sum_{x \in T} R(T_x)$, where $x$ goes over all vertices of $T$, and $T_x$ is the subtree induced by $x$ (consisting of $x$ and all of its progeny).

By shuffling the order of these trees and listing the first 5, the result might be $C(G), A(B(F)), B(D, E), A(B, C), C$.

I can already generate a full list of subtrees. For larger trees, this quickly becomes impossibly large. I am looking for a way of generating these subtrees without having to generate all of them.

One possible method I've thought of is to keep a count of how many unseen rooted subtrees each of the nodes has left, and decrementing each time a subtree is generated from that node. The probability that a node is selected would be weighted by this counter. I would also have to prevent the generation of duplicates. I was wondering if there is a better way.