Find all the biconnected components, let there be $$$C$$$ such components.

Let $$$G$$$ be a graph with $$$C$$$ nodes. For some color $$$c$$$ let the indices of edges with such color be $$$c_1, c_2, \ldots, c_x$$$, let's add edge $$$c_i-c_{i-1}$$$ for every $$$x \geq i \gt 1$$$ to $$$G$$$. If we do this for all colors we will have some connected components in $$$G$$$. It can be proven that for every connected component in $$$G$$$: we can have all the colors (in this component) in an optimal tree iff this component has a cycle or contains a vertex which corresponds to a bridge BCC in the original graph.

All of this can be done in linear time.