题意

可以转化为将树分割为不超过个连通块，每个连通块颜色不同,求方案数。

Solution

若将树分割为个连通块，则需要删去条边，故方案数为 。同时，要从种颜色中选出中颜色染色故方案数为 ，一共有个全排列。所以方案数有

综上，总的方案数为：

时间复杂度