题目传送门

题目解释

给定两个数 $n$，$k$，分别代表节点的个数和颜色的个数。求合法的染色方案，使得任何两个距离不大于 $2$ 的不同节点所被染的颜色不同。$ans$ 需要对 $10^{9}+7$ 取模。

题目分析

写在前面

本题通过 dfs 做，所以每一次对于节点 $k$，只考虑 $k$ 上面的节点对于 $k$ 的染色方案的影响。 在下面的分析中会出现数组：$fa_{k}$ 表示 $k$ 节点的父亲。

简化分析

一条链

显然，第一个节点的方案数为 $k$，第二个节点的方案数为 $(k-1)$，后面的节点的染色方案为 $(k-2)$。这个链的染色方案数为：$ans=k\times (k-1)\times (k-2)^{n-2}$

节点 $fa_{k}$ 第一个计算的节点

这个节点 $k$ 不用考虑 $fa_{k}$ 的其他儿子，所以方案数还是 $(k-2)$，当然，如果 $fa_{k}$ 是树的根节点，方案数即为 $(k-1)$。

节点 $fa_{k}$ 然后计算的节点

显然， $k$ 的方案数为 $(k-2-x)$，$x$ 代表在 $k$ 前面计算过的 $fa_{k}$ 的子节点。（因为与 $k$ 节点距离不大于2的节点除了 $fa_{k}$ 和 $fa_{fa_{k}}$，只有 $fa_{k}$ 的其他子节点。）

所以

这棵树和它的子树都可以通过类似的方法用 dfs 递归下去，所以本题是一道简简单单的递归题。

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
const int mod=1e9+7;
int n,k;
int ans=1;
int head[MAXN],tot;
struct edge{
	int to,nxt;
}e[MAXN<<1];
void edgeadd(int u,int v){
	e[++tot].nxt=head[u];
	e[tot].to=v;
	head[u]=tot;
}
int cnt[MAXN];
void dfs(int u,int fa,int sum){
	ans=(ans*max(0ll,k-sum)%mod)%mod;
	cnt[u]++;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v!=fa){
			cnt[v]++;
			dfs(v,u,cnt[u]);
			cnt[u]++;
		}
	}
}
signed main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		edgeadd(u,v);
		edgeadd(v,u);
	}
	dfs(1,0,0);
	cout<<ans;
}