【每日一题】4月7日题目精讲 树
树
https://ac.nowcoder.com/acm/problem/13611
时间限制: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; }