题目链接：https://codeforces.com/contest/1825/problem/D1
赛时没过的题，主要不会的点在于k=2的情况。
思路：当k = 1 或者 k = 3 时，可以证明答案永远为1，可以画个图看看。
当k = 2 时，答案为所有选中的两个点的距离加一之和。
一共有n(n-1)/2种选法，直接暴力必TLE。
所以我们考虑每条边对答案的贡献。
假设有一条边x，它左边有a个点，右边有b个点，这条边就可以做出ab的贡献。
不要忘了，答案为所有选中的两个点的距离加一之和，所以答案等于所有边的贡献+n*(n-1)/2。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 200010,mod = 1e9+7;
vector<int>M[N];
int h[N],ne[2*N],num[2*N],idx;
int sz[N],n,k;
long long ans;
long long qmod(long long x,long long y){
long long ans = 1;
while(y){
if (y&1) ans = ans*x%mod;
x = x*x%mod;
y = y>>1;
}
return ans;
}
void add(int x,int y){
num[idx] = y,ne[idx] = h[x],h[x] = idx++;
}
void dfs(int u,int fa){
M[u].push_back(1);
sz[u] = 1;
for (int i=h[u];i!=-1;i=ne[i]){
int v = num[i];
if (v==fa) continue;
dfs(v,u);
ans = (ans+1ll*sz[v]*(n-sz[v]))%mod;
sz[u] += sz[v];
}
}
void solve(){
cin>>n>>k;
idx = 0;
memset(h,-1,sizeof(h));
for (int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
if (k==1||k==3) cout<<1<<'\n';
else{
dfs(1,-1);
long long sum = 1ll*n*(n-1)/2;
sum = sum%mod;
ans = (ans+sum)*qmod(sum,mod-2)%mod;
cout<<ans<<'\n';
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
T = 1;
while(T--) solve();
return 0;
}