网站开发外包 合同,二次开发需要源代码吗,wordpress技术类主题,wordpress 网站 seo题干#xff1a;
shy有一颗树#xff0c;树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的#xff0c;当且仅当对于所有相同颜色的点对(x,y)#xff0c;x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。
输入描述:
第一行两个整数n#xf…题干
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。
解题报告
一句话题解因为树上的任意两个点都是可以两两联通的而染色的过程就是构造联通快的过程即将一颗树拆分成若干子树。 其实分析一下就是求个连通块每一个子树都当成一个连通块最后然你求构成连通块的方案数所以这题边的读入根本无所谓我们不去关心因为就算树不是同一种状态但是因为染色使用的颜色数和每种颜色对应染的节点数只要相同我们就认为是一种相同的方案。
dp[i][j]表示用i个点染j种颜色的方案数。状态转移选择新开一个颜色或者和上一个节点用一个颜色也就是在一个连通块内不在一个连通块内。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
const ll mod 1e97;
ll dp[505][505];
int main()
{int n,k;cinnk;for(int a,b,i 1; in-1; i) {scanf(%d%d,a,b);} for(int i 1; in; i) {for(int j 1; jk; j) {if(i1 j1) dp[i][j]k;else dp[i][j] (dp[i-1][j] dp[i-1][j-1] * (k-(j-1)))%mod;}}ll ans 0;for(int j 1; jk; j) {ans (ans dp[n][j])%mod;}printf(%lld\n,ans);return 0 ;}
