題意：

給定一棵n個節點的樹，從1到n標號。選擇k個點，你需要選擇一些邊使得這k個點通過選擇的邊聯通，目標是使得選擇的邊數最少。

現需要計算對于所有選擇k個點的情況最小選擇邊數的總和為多少。

樣例解釋：

一共有三種可能:(下列配圖藍色點表示選擇的點，紅色邊表示最優方案中的邊)

選擇點{1,2}:至少要選擇第一條邊使得1和2聯通。

選擇點{1,3}:至少要選擇第二條邊使得1和3聯通。

選擇點{2,3}:兩條邊都要選擇才能使2和3聯通。

第一行兩個數n，k(1<=k<=n<=100000)接下來n-1行，每行兩個數x,y描述一條邊(1<=x,y<=n)Output
一個數，答案對1,000,000,007取模。Input示例
3 21 21 3Output示例
4
思路：
這題我實在是太蠢了，最后臨門一腳GG了。首先想到算邊的貢獻。這里只要知道一條邊(u,v)左右各有x，y個節點。只要左邊和右邊都有節點被選中，這條邊貢獻就要+1。這里求出x和y中一共選取k個的情況數，這里我蠢了，正面考慮這個問題感覺復雜度很高，卻沒有反應過來，應該直接從反面考慮，只要拿總的情況數-k全部屬于x的情況數-k全部屬于y的情況數即可。最最簡單的容斥思想啊。。。沒救了，智商真的低剩下的就是組合數，逆元處理。
代碼：
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAXN = 1e5 + 10;const ll MOD = 1e9 + 7;int m, k;ll ans;ll fac[MAXN], inv[MAXN];vector <int> tree[MAXN];ll pow_mod(ll a, ll n) {    ll res = 1;    while (n) {        if (n & 1) res = res * a % MOD;        a = a * a % MOD;        n >>= 1;    }    return res;}void init(int n) {    fac[0] = 1;    for (int i = 1; i <= n; i++) {        fac[i] = fac[i - 1] * i % MOD;        inv[i] = pow_mod(fac[i], MOD - 2);       //PRintf("%d : %I64d %I64d/n", i, fac[i], inv[i]);    }}ll C(int x, int y) {    if (y > x) return 0;    if (x == y) return 1;    return fac[x] * inv[y] % MOD * inv[x - y] % MOD;}int dfs(int u, int pre) {    int cnt = tree[u].size(), res = 1;    for (int i = 0; i < cnt; i++) {        int v = tree[u][i];        if (v == pre) continue;        int sonnum = dfs(v, u);        ans = (ans + C(m, k) - C(sonnum, k) - C(m - sonnum, k) + 2 * MOD) % MOD;        res += sonnum;    }    return res;}int main() {    scanf("%d%d", &m, &k);    init(m);    for (int i = 1; i < m; i++) {        int u, v;        scanf("%d%d", &u, &v);        tree[u].push_back(v);        tree[v].push_back(u);    }    ans = 0;    dfs(1, -1);    printf("%I64d/n", ans);    return 0;}