What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not
Why should we even expect that there is such a polynomial-time algorithm? The comment


  Do you know how to solve this without the colors? That would be a good start. – Yuval Filmus Jun 15 '19 at 14:24


has an upvote, but it only hints implicitly that there is a (simple?) solution. Let me try to guess the (simple?) solution that is expected here. The AHU algorithm by Aho, Hopcroft and Ullman produces a canonical labeling of trees. Let's interpret the AHU algorithm as an efficient implementation of color refinement for rooted trees, and ask whether color refinement for "labeled trees" (isomorphism of "colored trees" would not allow to swap colors) would always be able to decide isomorphism. The answer is "no", because isomorphism of labeled trees is GI complete:


  From a graph G, construct a rooted labeled tree T by putting a node below the root of the tree for every vertex of G. For every edge of G, put two nodes with the same label on the next lower level. An edge has two endpoints, connect the corresponding vertices (or rather the tree nodes corresponding to them) each with one of the tree nodes corresponding to the edge.
  


The link above also makes it clear that this is well known by citing


  
    Theorem: Marked tree isomorphism is isomorphism complete
  
  
  from section 6.4 Marked Graphs and Marked Trees in Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo. They used the definition that “A marked graph is a graph together with a partition of its vertices. An isomorphism of marked graphs is an isomorphism of the underlying graphs which preserves the partitioning.”