【题目链接】点击打开链接

【题意】中文题目

【解题方法】

我们考虑每一条边对答案的贡献。假如这条边一边有a个节点，另一边有b个节点。那么如果我要选中这一条边，我就必须要在两边都选上至少一个节点，且选的节点总个数等于k。
我们考虑反面，就是只在一边选k个点，显然方案数是C(a,k)+C(b,k)
总方案数是C(n,k)
所以每条边的贡献等于C(n,k)-(C(a,k)+C(b,k))
把每条边的贡献累加起来，就是最后的答案


【AC代码】

//
//Created by just_sort 2016/1/3
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
const int maxn = 1e5 + 10;
const int maxm = 2e5;
const int maxs = 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);}
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
LL fac[maxn];
void init1(){
    fac[0] = 1LL;
    REP1(i, 1, maxn) fac[i] = fac[i - 1] * i % mod;
}
LL powmod(LL a, LL n){
    LL res = 1, temp = a % mod;
    while(n){
        if(n & 1) res = res * temp % mod;
        temp = (temp % mod) * (temp % mod) % mod;
        n >>= 1;
    }
    return res;
}
LL C(int n, int m){
    if(m > n) return 0;
    return fac[n] * powmod(fac[m] * fac[n - m] % mod, mod - 2) % mod;
}
LL Lucas(int n, int m){
    if(m == 0) return 1;
    return C(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod;
}
struct edge{
    int v, next;
    edge(){}
    edge(int v, int next) : v(v), next(next) {}
}E[maxn * 2];
int head[maxn], edgecnt;
void init2(){
    edgecnt = 0;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v){
    E[edgecnt].v = v, E[edgecnt].next = head[u], head[u] = edgecnt++;
}
int sz[maxn];
LL ans, cnt;
int n, k;
void dfs(int u, int fa)
{
    sz[u] = 1;
    for(int i = head[u]; ~i; i = E[i].next){
        int v = E[i].v;
        if(v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
    ans += cnt - Lucas(1LL*sz[u], 1LL*k) - Lucas(1LL*(n - sz[u]), 1LL*k);
    ans %= mod;
}
int main()
{
    init1();
//    while(scanf("%d%d", &n, &k) != EOF)
//    {
        cin >> n >> k;
        init2();
        REP1(i, 1, n){
            int u, v;
            scanf("%d%d", &u, &v);
            addedge(u, v);
            addedge(v, u);
        }
        cnt = Lucas(n, k);
        dfs(1, -1);
        cout << (ans + mod) % mod << endl;
 //   }
    return 0;
}