Description
一个n个节点的树。
现在用k种颜色，给树上的每个节点染色
要求:
任何两个距离不大于2的不同节点被染的颜色不同。
由于答案可能过大，请将其对10^9+7取模。
Format
Input
第一行一个数n,k，含义如题
接下来共有n-1行，两个数u,v表示u和v之间存在一条边
1≤n,k≤1e5,
Output
如题
Samples
输入数据 1
4 3
1 2
2 3
3 4
Copy
输出数据 1
6思路
可以用小学学的乘法原理，算出每个点染的色有几种可能性，最后一起乘就行了。
那么，怎么算出每个点染的色有几种可能性呢？
首先，对于该树的根（1号节点）肯定有k种染色方法。
然后对于1号节点的子节点，肯定就都有k-1种可能性了。
对吗？
我们来考虑一个问题：如果1号节点拥有的子节点数>1的话，那么第一个被遍历到的子节点有k-1种可能，这没错。但是第二个呢？它不仅不能与父节点的颜色相同，而且还不能与兄弟节点重合，所以它只有k-2种可能，以此类推的话， 第三个被遍历到的子节点有k-3种可能，第四个被遍历到的子节点有k-4种可能……
所以总结出来一个公式:
如果当前节点所遍历到的第一个子节点有x种染色方法，那么第n个子节点就有x-n+1种染色方法
那么处理完兄弟节点之间的关系，我们再来看看父子的关系。
当遍历到深度为3(根节点深度为1)的节点时， 第一个节点就只有k-2种可能(因为它有爷爷节点了)。
那么思考一下:当遍历到深度为4的节点时， 第一个节点是有k-3种可能吗？这里十分易错，需要思考清楚。
显然，此时第一个节点就还是只有k-2种可能。那么这就好办了。
总结一下我们的结论:
- 如果当前节点所遍历到的第一个子节点有x种染色方法，那么第n个子节点就有x-n+1种染色方法
- 如果当前节点深度为1，则x=k
- 如果当前节点深度为2，则x=k-1
- 如果当前节点深度>2，则x=k-2
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,k,u,v,a[10000001],ans = 1,mod = 1e9 + 7;
vector<int> 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()
{
cin>>n>>k;
for(int i = 1;i < n;i++)
{
cin>>u>>v;
vec[u].push_back(v);
vec[v].push_back(u);
}
dfs(0,1,1,0);
for(int i = 1;i <= n;i++)
{
//cout<<a[i]<<' ';
if(a[i] <= 0)
{
ans = 0;
break;
}
ans = (ans * a[i]) % mod;
}
cout<<ans;
return 0;
}解压
如果这篇博客对您有帮助的话，请点赞关注收藏支持一下吖！(≧∇≦)ﾉ
