I can do it in $O(n^2)$ per tree.
The number of possible trees is $(n+1)^{n-1}$, since choosing a tree in your problem is equivalent to choosing an undirected tree on the vertex set $v\cup \{r\}=\{v_1,\dots,v_n,r\}$, and then directing all edges towards the root. The number of undirected trees on $n+1$ vertices is $(n+1)^{n-1}$ (this is Cayley's theorem), and these trees can be generated efficiently using Prüfer codes.
Specifically, iterate through all lists of length $n-1$ with entries in $\{0,1,2,\dots,n\}$, where $0$ represents $r$ and $1$ through $n$ represent $v_1$ through $v_n$. For each list, generate the corresponding tree with vertices $\{r,v_1,\dots,v_n\}$ using the algorithm to convert a Prüfer sequence into an undirected tree. Finally, turn this into a directed tree using breadth first search starting from vertex $r$.
Yes, because a tiebreaker can be modeled as changing the edge weights very slightly to make all edge weights unique.
Suppose that edges $e_1, e_2, \dots, e_m$ have weights $w_1, w_2, \dots, w_m \in \mathbb R$. Let $\epsilon$ be the smallest difference between two distinct edge weights. Suppose also that we've written edges $e_1, e_2, \dots, e_m$ in the tiebreaking order: whenever we are choosing between edges $e_i$ and $e_j$ with the same weight, we pick $e_i$ if $i<j$ and $e_j$ otherwise.
This decision process is equivalent to the decision process where edge $e_i$ has weight $w'_i = w_i + \frac{i}{2m} \cdot \epsilon$. The weights $w_1', w_2', \dots, w_m'$ are all unique, but comparing $w_i'$ and $w_j'$ is equivalent to comparing $w_i$ and $w_j$ when $w_i \ne w_j$. Only when $w_i = w_j$ does the extra term $\frac{i}{2m} \cdot \epsilon$ come into effect, and using it to compare is equivalent to using the tiebreaker.
So Kruskal with tiebreaks is equivalent to Kruskal with weights $w_1', \dots, w_m'$. This is equivalent to Prim with weights $w_1', \dots, w_m'$, because there is only one MST when weights are unique. That, in turn, is equivalent to Prim with the same tiebreaks.
Best Answer
:-) OK, you are looking worthy so I reveal to you a secret which may be not known to these graph theorists who did not study matrix theory: each symmetric square matrix $A=\|a_{ij}\|$ with zeroes on the diagonal (in particular, any adjacency matrix of a finite simple graph) can be represented as $A=N+N^T$, where $N=\|n_{ij}\|$ is nilponent (for each $i,j$ we put $n_{ij}=a_{ij}$, if $i<j$ and $n_{ij}=0$, otherwise).