欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-16 19:27:47
...

时间限制: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;
}
相关标签: 算法