江苏省城乡和住房建设厅网站首页,企业信息查询系统官网江苏,南京网站维护,手机网站用什么语言开发Description
一个n个节点的树。
现在用k种颜色#xff0c;给树上的每个节点染色
要求:
任何两个距离不大于2的不同节点被染的颜色不同。
由于答案可能过大#xff0c;请将其对10^97取模。
Format
Input
第一行一个数n,k#xff0c;含义如题
接下来共有n-1行#x…Description
一个n个节点的树。
现在用k种颜色给树上的每个节点染色
要求:
任何两个距离不大于2的不同节点被染的颜色不同。
由于答案可能过大请将其对10^97取模。
Format
Input
第一行一个数n,k含义如题
接下来共有n-1行两个数u,v表示u和v之间存在一条边
1≤n,k≤1e5,
Output
如题
Samples
输入数据 1
4 3
1 2
2 3
3 4Copy
输出数据 1
6 思路
可以用小学学的乘法原理算出每个点染的色有几种可能性最后一起乘就行了。
那么怎么算出每个点染的色有几种可能性呢
首先对于该树的根1号节点肯定有k种染色方法。
然后对于1号节点的子节点肯定就都有k-1种可能性了。
对吗
我们来考虑一个问题如果1号节点拥有的子节点数1的话那么第一个被遍历到的子节点有k-1种可能这没错。但是第二个呢它不仅不能与父节点的颜色相同而且还不能与兄弟节点重合所以它只有k-2种可能以此类推的话 第三个被遍历到的子节点有k-3种可能第四个被遍历到的子节点有k-4种可能……
所以总结出来一个公式: 如果当前节点所遍历到的第一个子节点有x种染色方法那么第n个子节点就有x-n1种染色方法 那么处理完兄弟节点之间的关系我们再来看看父子的关系。
当遍历到深度为3(根节点深度为1)的节点时 第一个节点就只有k-2种可能(因为它有爷爷节点了)。
那么思考一下:当遍历到深度为4的节点时 第一个节点是有k-3种可能吗这里十分易错需要思考清楚。
显然此时第一个节点就还是只有k-2种可能。那么这就好办了。
总结一下我们的结论: 如果当前节点所遍历到的第一个子节点有x种染色方法那么第n个子节点就有x-n1种染色方法如果当前节点深度为1则xk如果当前节点深度为2则xk-1如果当前节点深度2则xk-2 代码
#include bits/stdc.h
#define int long long
using namespace std;
int n,k,u,v,a[10000001],ans 1,mod 1e9 7;
vectorint vec[1000001];
void dfs(int fa,int x,int dp,int p)
{int se k;if(dp 1) se--;if(dp 2) se--;a[x] se - p;a[x] % mod;p 0;for(int i 0;i vec[x].size();i)if(vec[x][i] ! fa){dfs(x,vec[x][i],dp 1,p);p;}
}
signed main()
{cinnk;for(int i 1;i n;i){cinuv;vec[u].push_back(v);vec[v].push_back(u);}dfs(0,1,1,0);for(int i 1;i n;i){//couta[i] ;if(a[i] 0){ans 0;break;}ans (ans * a[i]) % mod;}coutans;return 0;
} 解压
如果这篇博客对您有帮助的话请点赞关注收藏支持一下吖(≧∇≦)
