  For any small constant $\epsilon>0$, the Erd\H{o}s-R\'enyi random graph
$G(n,\frac{1+\epsilon}{n})$ with high probability has a unique largest
component which contains $(1\pm O(\epsilon))2\epsilon n$ vertices. Let
$G_c(n,p)$ be obtained by assigning each edge in $G(n,p)$ a color in $[c]$
independently and uniformly. Cooley, Do, Erde, and Missethan proved that for
any fixed $\alpha>0$, $G_{\alpha n}(n,\frac{1+\epsilon}{n})$ with high
probability contains a rainbow tree (a tree that does not repeat colors) which
covers $(1\pm O(\epsilon))\frac{\alpha}{\alpha+1}\epsilon n$ vertices, and
conjectured that there is one which covers $(1\pm O(\epsilon))2\epsilon n$. In
this paper, we achieve the correct leading constant and prove their conjecture
correct up to a logarithmic factor in the error term, as we show that with high
probability $G_{\alpha n}(n,\frac{1+\epsilon}{n})$ contains a rainbow tree
which covers $(1\pm O(\epsilon\log(1/\epsilon)))2\epsilon n$ vertices.
