 Solution

Root the tree at any vertex and order vertices so every parent precedes its children. The root has $k$ colour choices. Each of the other $n-1$ vertices has exactly one earlier adjacent vertex, its parent, and therefore exactly $k-1$ choices. There are no other restrictions because a tree has no cycles and no extra edges between those branches. Multiplication yieldsThe formula also includes the one-vertex tree.