首页 > 试题广场 >

树

[编程题]树
  • 热度指数：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。
算法知识视频讲解
添加回答
元气の悟空头像 元气の悟空 
#include<stdio.h>
const int maxn=300+5,mod=1e9+7;
long long dp[maxn][maxn],res=0;
int main(){
    int n,k,i,j,x,y;
    for(scanf("%d%d",&n,&k),i=0;i<n;i++) scanf("%d%d",&x,&y);
    for(dp[0][0]=1,i=1;i<=n;i++)
        for(j=1;j<=k;j++){
            dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*(k-j+1))%(long long)mod;
            if(i==n) res=(res+dp[i][j])%(long long)mod;
        }
    printf("%lld\n",res);
}

发表于 2017-11-14 16:41:01 回复(0)
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)
小小小小小.....头像 小小小小小.....
#include<iostream>
using namespace std;
const int mod= 1e9+7;
int main(){
int n,k;
cin>>n>>k;
int a,b; 
for(int i=1;i<n;i++){
cin>>a>>b;   //不影响结果 
}
long long int dp[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);  
//把这棵树展开，那么第n条边要么和第n-1条边颜色相同，要么不同，不同的话颜色还有(k-j+1) 种选择；
dp[i][j]=dp[i][j]%mod;
}
}
long long int ans =0;
for(int i=1;i<=k;i++){
ans+=dp[n][i];
ans=ans%mod;
}
cout<<ans<<endl;
} 
发表于 2017-08-28 19:51:02 回复(4)
提交观点

问题信息

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

热门推荐

通过挑战的用户

相关试题

树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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