【每日一题】4月7日题目精讲 树

树

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K
其他语言262144K
64bit IO Format:%lld

题目描述

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。
题解：
shy爹有棵树
这个题也可以这么想，把相同颜色当成一个整体，连通块，问构成连通块的方案
我们用dp来计数
dp[i][j]表示i个点用了j个颜色的方案
那么转移方程就是
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(k-(j-1))
dp[i][j]=第i个点和第i-1个点颜色相同或者第i-1个点所用的颜色与之前不同，之前用了（j-1）个颜色，这个点可用的颜色种类就是k-（j-1）
（可以理解成前者在一个连通块，后者不在一个连通块内）
因为数据给的肯定是棵树，那树的形状并不会影响结果，所以。。。也可以不输入那（n-1）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=303;
ll mod =1e9+7;
ll dp[maxn][maxn];
int n,k;
ll sum=0;
int main()
{
	cin>>n>>k;
	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;
		}
	}
	for(int i=1;i<=k;i++)
	{
		sum=(sum+dp[n][i])%mod;
		
	}
	printf("%lld",sum);
	return 0;
}