The following algorithm should efficiently calculate the answer for the number of subtrees of a labeled graph.
Let $(T, r)$ be a labeled, rooted tree with root $r$. We first calculate the number of subtrees containing $r$. Call this value $N_1(T, r)$. If $r_1, \dots, r_k$ are the neighbors of $r$ and $T_1,\dots, T_k$ are the trees of $T-r$ such that $r_i \in V(T_i)$ for $1 \le i \le k$, then
$N_1(T, r) = \prod_1^k \left( N_1(T_i, r_i) + 1 \right).$
This follows because for each neighbor $r_i$ of $r$, we have a choice of $N_1(T_i, r_i)$ possible trees or alternatively, the empty tree.
This formula gives a recursive algorithm to calculate $N_t(T, r)$. Since the total number of vertices in the trees decreases in each iteration of the algorithm, we get an easy $O(n^2)$ bound on the run-time.
For a labeled tree $T$, let $N(T)$ be the number of distinct subtrees. Fix a leaf $v$ of $T$. Then $N(T) = N(T-v) + N_1(T, v)$. Thus, again we get a recursive algorithm with a bound of $O(n^3)$ on the run-time. It might be possible to get better bounds on the run-time of the algorithms.
The specific value of $N(T)$ will depend a lot on the tree $T$. For example, if $T$ is the path on
$n$ vertices, then $N(T) = O(n^2)$. Alternatively, if $T$ is the star on $n$ vertices, then $N(T) = O(2^n)$.
We can see any tree $T$ as the Hasse diagram of a poset whose smallest element is the root. I will freely identify the tree with the corresponding poset.
If we label by $i$ the $i$'th vertex added in the process, we get a rooted tree equipped with a linear extension, and each such equipped rooted tree occur with probability $\frac{1}{(n-1)!}$ (where $n$ is the number of vertices).
The number of ways to get a given rooted tree in this way is the number of linear extensions of this tree up to automorphisms of the rooted tree.
Hence the probability you're looking for is given by
$$\frac{L(T)}{|\text{Aut}(T)| (n-1)!}$$
where $L(T)$ is the number of linear extensions of $T$ and $\text{Aut}(T)$ is the automorphism group of $T$.
There are algorithms for computing the former in $O(n^2)$ (https://www.researchgate.net/publication/226291352_On_computing_the_number_of_linear_extensions_of_a_tree). I am not sure for the latter, but it can probably be computed efficiently using a variant of the AHU algorithm.
Best Answer
Is Theorem 6.4 of http://people.brandeis.edu/~gessel/homepage/papers/enum.pdf what you want?