分析
按照 \(k\) 的奇偶分开考虑。
\(k\) 为奇数。一个好的节点有且仅有一个在任意两个有人的节点 \(i,j\) 的路径的交点上的最优位置。若该交点偏移 \(1\) 步，则必然会使路径长度和 \(+1\)。故期望为 \(1\)。
\(k\) 为偶数。任意一个好的节点仍然在任意两个有人的节点 \(i,j\) 的交点上。但若对于某个好点的偏移，在偏移后距离增加与减少的距离均为 \(\frac{k}{2}\) 时，这个点也是好的。考虑枚举边，若一条边的两边有人的点的数量均为 \(\frac{k}{2}\)，则这条边有贡献 \(1\)。即每条边的贡献之和为 \(\sum\limits_{u=1}^{n-1} \binom{siz_u}{\frac{k}{2}}\times \binom{n-siz_u}{\frac{k}{2}}\)。其中 \(siz_u\) 为边 \(u\) 左端的节点数量。但是，对于某一条有好点的路径 \(x\)，其中的边的数量总会比点的数量少一，所以贡献之和还需要加上 \(\binom{n}{k}\)。所以对于 \(k\) 为偶数时，期望为 \(\frac{\sum\limits_{u=1}^{n-1} \binom{siz_u}{\frac{k}{2}}\times \binom{n-siz_u}{\frac{k}{2}}+\binom{n}{k}}{\binom{n}{k}}\)。
注：求组合数可以先预处理 \(1 \le i \le n\) 的阶乘，在用逆元乘。在 \(siz_u+1 \le \frac{k}{2}\) 的时候，这条边是没有贡献的。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
const int N=1e6+10,p=1e9+7;
int n,k;
int ne[N],e[N],h[N],idx;
int sum,siz[N],__[N];
il int qmi(int a,int b){
int ans=1;
while(b){
if(b&1) ans=ans*a%p;
a=a*a%p,b>>=1;
}
return ans;
}
il int C(int n,int m){
if(n<m) return 0;
return __[n]%p*qmi(__[m],p-2)%p*qmi(__[n-m],p-2)%p;
}
il void add(int a,int b){ne[++idx]=h[a],e[idx]=b,h[a]=idx;}
il void dfs(int now,int fa){
siz[now]=1;
for(re int i=h[now];i;i=ne[i]){
int j=e[i];if(j==fa) continue;
dfs(j,now),siz[now]+=siz[j];
}
return ;
}
il void dfs2(int now,int fa){
for(re int i=h[now];i;i=ne[i]){
int j=e[i];if(j==fa) continue;
sum=(sum+C(siz[j],k/2)*C(n-siz[j],k/2))%p;
dfs2(j,now);
}
return ;
}
il void solve(){
cin>>n>>k;
for(re int i=1,u,v;i<n;++i)
cin>>u>>v,
add(u,v),add(v,u);
if(k&1){cout<<"1\n";return;}
__[0]=1;for(re int i=1;i<=n+5;++i) __[i]=__[i-1]*i%p;
sum=C(n,k);
dfs(1,0),dfs2(1,0);
cout<<(sum%p*qmi(C(n,k),p-2)%p)%p<<"\n";
return ;
}
signed main(){
solve();
return 0;
}