Let's take some leaf-vertex in this tree and root the tree in this vertex. Now each vertex has no more that N-1 children.

Let's define dynamic programming on subtrees with state dp[v][c] - the mimimal cost to color subtree rooted at veretx v with condition that there is no edge from v to its childred of color c. The answer will be minimum over all values dp[root][c] for each possible c.

How to calculate this values? Consider some concrete value dp[v][c]. We can create table A of size childrens(v) x c where A[i][j] equals dp[ children[v][i] ][j] + cost[j]. We know that we should choose different colors for each edge from v to its children (it's convinient to assume that cost[c] equals infinity in such case). So we have several children and we should assign different colors for them to miminize the total cost. It looks very similar to classic assignment problem which can be solved in O(NMM) by Hungarian algorithm, isn't it. So for each value dp[v][c] we create such table and run Hungarian algorithm on it and dp[v][c] equals to the minimal cost of assignment.

The total time complexity is O(N4).