网站开发要求,wordpress评论显示数字ip,响应式网页模板制作,加查网站建设树 时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 131072K 其他语言262144K 64bit IO Format:%lld 题目描述 shy有一颗树#xff0c;树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的#xff0c;当且仅当对于所有相同颜色的点…树 时间限制C/C 1秒其他语言2秒 空间限制C/C 131072K 其他语言262144K 64bit IO Format:%lld 题目描述 shy有一颗树树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的当且仅当对于所有相同颜色的点对(x,y)x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。 输入描述: 第一行两个整数nk代表点数和颜色数 接下来n-1行每行两个整数x,y表示x与y之间存在一条边 输出描述: 输出一个整数表示方案数mod 1e97。 示例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
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn303;
ll mod 1e97;
ll dp[maxn][maxn];
int n,k;
ll sum0;
int main()
{cinnk;for(int i1;in;i){for(int j1;jk;j){if(i1j1){dp[i][j]k;}else dp[i][j](dp[i-1][j]dp[i-1][j-1]*(k-(j-1)))%mod;}}for(int i1;ik;i){sum(sumdp[n][i])%mod;}printf(%lld,sum);return 0;
}
