Recovering species from a phylogenetic tree
I present an algorithm for the tree case. The algorithm solves the problem in two 'passes' through the tree: first from leaves to root, then from the root to the leaves.



Algorithm:
First, we augment our tree $T$ with the additional field $v.subcolors$ for each vertex $v$. This field should contain the set of all colors present in the subtree rooted at $v$ (with $v$ included). 

We traverse the tree 'layer by layer' from leaves to the root: Our first layer consists of all leaves. The next layer is constructed by taking the set of parents from all vertices in the current layer, which we repeat until we reach the root. 

Then, we fill in the field $v.subcolors$ for all vertices $v$ in our layer. This is easy to do, as we know that $w.subcolors$ is already set for all children of $v$, as those belong to the previous layer we've already visited.

Observe that some vertex $v$ must be of color $c$ if and only if it separates two vertices of color $c$, i.e. it lies on the (unique!) path between two vertices of color $c$. We can determine whether $v$ separates some vertices easily if we know what colors lie in the components formed by removing $v$ from the tree: if the color $c$ lies in two distinct such components, $v$ must separate some vertices in those components. 

We can efficiently find the colors in the subtree of the children of $v$, as that is given by $v.subcolors$. The parent of $v$ is a bit more tricky. However, if the parent has already been colored with color $c$, $v$ can be a separator of some vertex the component of the parent only if that vertex has color $c$! Otherwise, if there were some other color $c'$, the parent of $v$ would also separate those vertices. But the parent has color $c$, which means that the coloring of the parent of $v$ is incorrect. This contradicts our assumption that we know the correct color of the parent (note that we have assumed a valid coloring exists!) 

So, we can now color the vertices by traversing the tree from root to leaves, again layer by layer: we check at each vertex $v$ whether it separates vertices of some color (as a valid coloring exists, this is at most once color) and fill in that color. If it separates no vertices of the same color, we simply give it an unused color from $[1,n]$.



Efficiency: Coloring the sub-tree requires traversing the tree from bottom to top. As we need to compute with the field $v.subcolors$ at most once for every edge in the tree, this part takes $O(|E|) = O(|V|) = O(n)$ time.

For the down-traversal, we must perform a comparison again for each edge. We can check for each color and vertex adjacent to $v$ whether it occurs and see if it is a separator if it occurs twice. This takes $O(\mathrm{degree}(v)\cdot |C|)$ time if we store the color sets in a hash-table, where $|C|=n$, the number of colors. As the average degree of a tree is constant, performing this operation on all vertices takes $O(n^2)$ time.

So, in total, the algorithm runs in $O(n^2)$ time. This turned out to be fast enough for the testcases given in the contest.

This time could maybe be improved by using an efficient union algorithm to check the separator more efficiently. (Union-find doesn't seem to do the trick, as the sets aren't disjoint)