https://ac.nowcoder.com/acm/problem/13611

题意

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

Solution

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

综上,总的方案数为:

时间复杂度

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务