首页 > 试题广场 >

树

[编程题]树
  • 热度指数：34 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
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。
算法知识视频讲解
添加回答
Java
剩一口头像 剩一口
package Algorithm;

import java.util.Scanner;

public class 树 {
public static final int mod= (int) (1e9+7);
public static void main(String[] args) {
// TODO Auto-generated method stub
int n,k;
Scanner in = new Scanner(System.in);
n=in.nextInt();
k=in.nextInt();
int a,b;
for(int i =1;i<n;i++){
a=in.nextInt();
b=in.nextInt();
}
long dp[][] = new long[500][500];
dp[0][0]=1;
for(int i =1;i<=n;i++)
for(int j=1;j<=k;j++){
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(k-j+1);
dp[i][j] = dp[i][j]%mod;
}
long ans = 0;
for(int i = 1;i<=k;i++){
ans+=dp[n][i];
ans%=mod;
}
System.out.println(ans);
}


}

发表于 2017-08-29 21:10:08 回复(0)
提交观点

问题信息

组合数学 树
上传者：牛客301599号
难度：
1条回答 4363浏览

热门推荐

通过挑战的用户

相关试题

树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号