题干：
 

shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。

输入描述:

第一行两个整数n，k代表点数和颜色数；
接下来n-1行，每行两个整数x,y表示x与y之间存在一条边；

输出描述:

输出一个整数表示方案数（mod 1e9+7）。

示例1

输入

复制

4 3
1 2
2 3
2 4

输出

复制

39

备注:

对于30%的数据，n≤10, k≤3；
对于100%的数据，n,k≤300。

解题报告：

一句话题解：因为树上的任意两个点都是可以两两联通的，而染色的过程就是构造联通快的过程，即将一颗树拆分成若干子树。

   其实分析一下就是求个连通块（每一个子树都当成一个连通块，最后然你求构成连通块的方案数，，所以这题边的读入根本无所谓，我们不去关心，，因为就算树不是同一种状态，，但是因为染色使用的颜色数和每种颜色对应染的节点数只要相同，我们就认为是一种相同的方案。）

dp[i][j]表示用i个点染j种颜色的方案数。状态转移：选择新开一个颜色，或者和上一个节点用一个颜色（也就是：在一个连通块内，不在一个连通块内。）

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
const ll mod = 1e9+7; 
ll dp[505][505];
int main()
{
	int n,k;
	cin>>n>>k;
	for(int a,b,i = 1; i<=n-1; i++) {
		scanf("%d%d",&a,&b);
	} 
	for(int i = 1; i<=n; i++) {
		for(int j = 1; j<=k; j++) {
			if(i==1 &&j==1) dp[i][j]=k;
			else  dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] * (k-(j-1)))%mod;
		}
	}
	ll ans = 0;
	for(int j = 1; j<=k; j++) {
		ans = (ans + dp[n][j])%mod;
	}
	printf("%lld\n",ans);
	return 0 ;
 }