T368027 树上染色（colour）

【问题描述】 给定一颗树,树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的当且仅当相同颜色的点构成树上的一个连通块。问有多少种合法的染色方案 【输入格式】 第一行两个整数n，k代表点数和颜色数 接下来n-1行，每行两个整数x,y表示x与y之间存在一条边 【输出格式】 一个整数代表方案数，答案对1e9+7取模 【输入样例】 4 3 1 2 2 3 2 4 【输出样例】 39 【数据范围】 对于30%的数据，n,k≤6 对于所有数据，n,k≤1000

无

无

无