题意很明确了，大意就是一棵树，染色，距离 $\le 2$ 不得染同色，问染色方案。
首先我们要明确，距离 $\le 2$，具体是什么情况呢？
显然，分两个大类：
-
一条链往下
- 某节点和它的儿子
- 某节点和它的孙子
-
非一条链往下
- 某节点和它的兄弟
那么我们就梳理出了 $3$ 中不能涂同一种颜色的情况。
读到这里，我想应该正解慢慢出来了。
其次我们要知道，总染色方案就是每个点染色方案之积。
那么每个点最初有 $k$ 种选择，我们看一下它是否存在爷爷，若存在最多只有 $k-2$ 种，因为有爷爷必然有爸爸。
一条链往下的方案已经考虑完了，接下来考虑兄弟。
兄弟就很简单了，记一个变量，自己的父亲每往下搜索一次加一，既能得到兄弟的个数。
详情见代码。
代码
#include<bits/stdc++.h>
using namespace std;
const int p=1000000007;
int n,k,u,v;
long long ans=1;//十年OI一场空，不开long long见祖宗
bool vis[100020];
vector<int>a[100020];
void dfs(int u,int tmp)//u表示目前节点 tmp表示当前节点涂色数量
{
ans*=tmp;//乘上方案数
ans%=p;//十年OI一场空，忘记取模见祖宗
vis[u]=1;//遍历基本操作，也可以记录father
int cnt=0;
for(auto v:a[u])
{
if(vis[v])continue;
int w=(u==1?k-1:k-2);//如果是自己根，自己的儿子没有爷爷，反之肯定有爷爷
//上一条语句也可以写成dfs多带个dep参数，记录深度
w-=cnt;//去除自己的兄弟所要染色的情况
dfs(v,w);//继续搜索
cnt++;//兄弟+1
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
//建边基本操作，也可以单向
}
dfs(1,k);//开始搜索
printf("%d\n",(int)ans);
return 0;
}