Before revision:  In this work, we  introduce the first fully polynomial time randomized approximation scheme (FPRAS) for counting the number of trees of size n accepted by a tree automaton, where n is given in unary , and the first polynomial time algorithm for sampling uniformly from this set of trees. Our results improve over the prior quasi-polynomial time randomized approximation scheme (QPRAS)and sampling algorithm of Gore, Jerrum, Kannan, Sweedyk, and Mahaney 97'. At the heart of our algorithm is a reduction to the problem of estimating the number of strings of length\neqP n accepted by a succinct non-deterministic finite automaton(NFA), which is an NFA where the transitions are labeled by succinctly encoded sets of symbols, whose sizes can be exponential in the encoding length.
After revision:  In this work, we introduce the first fully polynomial time randomized approximation scheme (FPRAS) for counting the number of trees of size n accepted by a tree automaton, where n is given in unary , and the first polynomial time algorithm for sampling answers uniformly from a query in C. As a corollary, it follows that a class of conjunctive queries over graphs admits an FPRAS if and only if it has bounded treewidth (unless BPP\neqP n accepted by a succinct non-deterministic finite automaton(NFA), which is an NFA where the transitions are labeled by succinctly encoded sets of symbols, whose sizes can be exponential in the encoding length.