Coloring A Tree

You have a tree consisting of n vertices. You want to color each vertex of the tree in one of the k colors such that for any pair of vertices having same color, all the vertices belonging to the path joining them should also have same color. In other words, for any two vertices u, v with same color, all the vertices in the path joining them should also have color same as that of the u (or same as