牛客网暑期ACM多校训练营（第三场）G BFS计数

题意：

给你一棵树，你可以对树进行染色，树的价值定义为最小的相同颜色的节点之间的距离，问你当树的价值为d的时候，有多少种染色方案。

我们可以转化一下题目，可以转变成当树的价值>=d时，有多少种方案，然后我们用>=d的方案数减去>=d+1的方案数就是价值刚好为d的方案数了。

怎么求树的价值>=d的方案数呢？这里可以看成对于任意一个节点，所有和它距离小于d的节点，不能和它有相同的颜色。

然后我们随便找个根节点开始bfs染色，怎么染色呢？

我们考虑根节点，它有k种颜色可以染，我们给根染了一种颜色之后，所有和根在距离<d的点，可以被染的颜色都会少一种，然后我们bfs对所有的节点都这样做，然后我们最后把每个点可以染的颜色种类数乘起来，就是我们需要的答案了。

上述思路代码实现应该是很简单的，因为数据范围只有5000，我们可以对每个点都dfs一次，求出所有点之间的距离。然后计算的时候每次都把距离<d的所有点可选颜色都-1。

代码实现不是主要部分，重点是为什么按照bfs的顺序去做可以保证答案正确呢？

这里就要考虑一个问题了。假如我们有两种颜色，每个节点不能和距离<=1的点有相同的颜色，我们要怎么做呢？

比如我们有三个节点

1->2->3

如果我们不按照bfs顺序来染色

1有两种染色方案，3也有两种染色方案，这样一看，2就没有染色方案了，最后乘出来的答案就会为0。这是为什么呢？

我们发现1和3可以选取的颜色有重复，然后作用到2这个节点就会出问题。

那么为什么bfs能保证答案正确呢？

我画了很久的图。。发现了一个性质。。

如果我们按照bfs的顺序来选择颜色计算方案数的话，已经选过颜色的和当前节点距离在d以内的节点，一定两两距离都在d以内，就是说，当前节点距离d以内的已经选择过颜色的节点在选择颜色种类的时候一定会互相考虑到彼此节点，如果我们用dfs，就保证不了这个性质了。

感谢牛客多校群的大佬帮我完成了这个证明

当前bfs到的节点和其它(bfs走过的&&到当前节点距离<d)的点，两两之间距离<d的证明如下：

dis(u,v)=dis(u,x)+dis(v,x)-2*dis(lca(u,v),x)
当前枚举点为x，u,v是任意点，lca是对于x为根
设u为深度比较低的那个点,
dis(u,x)-dis(lca(u,v),x)是大于等于dis(v,lca(u,v))的
然后代进去就能发现dis(u,v)<=dis(v,x)的

AC代码如下:

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const ll maxn = 5000+7;
ll n,k,d;
ll dis[maxn][maxn];
vector<ll>v[maxn];
void dfs(ll s,ll now,ll pre){
    for(ll i=0;i<v[now].size();i++){
        ll to=v[now][i];
        if(to==pre)continue;
        dis[s][to]=dis[s][now]+1;
        dfs(s,to,now);
    }
}
ll val[maxn];
ll solve(ll d){
    queue<ll>q;
    q.push(1);
    for(ll i=1;i<=n;i++)val[i]=k;
    ll ans=1;
    while(!q.empty()){
        ll i=q.front();q.pop();
        ll res=0;
        for(ll j=1;j<=n;j++)
            if(i!=j)
            val[j]-=dis[i][j]<d;
        if(val[i]<=0)return 0;
        ans=ans*val[i]%mod;
        //printf("[%lld]\n",val[i]);
        for(ll j=0;j<v[i].size();j++){
            ll to=v[i][j];
            if(dis[1][i]+1==dis[1][to]){
                q.push(to);
            }
        }
    }
    return ans;
}
int main()
{
    scanf("%lld%lld%lld",&n,&k,&d);
    for(ll i=1;i<n;i++){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(ll i=1;i<=n;i++){
        dfs(i,i,-1);
    }
    ll ans=(solve(d)-solve(d+1))%mod+mod;
    printf("%lld\n",ans%mod);
    return 0;
}