本文共 1780 字，大约阅读时间需要 5 分钟。

1677 treecnt

给定一棵n个节点的树，从1到n标号。选择k个点，你需要选择一些边使得这k个点通过选择的边联通，目标是使得选择的边数最少。

样例解释：

一共有三种可能:(下列配图蓝色点表示选择的点，红色边表示最优方案中的边)

输入

第一行两个数n，k(1<=k<=n<=100000)

输出

一个数，答案对1,000,000,007取模。

输入样例1

3 2

输出样例1

4

输入样例2

10 4

输出样例2

1386

#include 
   
    #define ll long longusing namespace std;const int maxn = 100005;const int mod = 1e9 + 7;struct node {
       int v, next;} tree[maxn * 2];int dp[maxn];int vis[maxn];int head[maxn * 2];ll n, k, num, answer = 0;// cbk[i]为C n kll cbk[maxn];ll QuickPow(ll x, ll N) {
       ll res = x;    ll ans = 1;    while (N) {
           if (N & 1) {
               ans = ans * res % mod;        }        res = res * res % mod;        N = N >> 1;    }    return ans;}// 1/all getInv(ll a) {
       return QuickPow(a, mod - 2);}void add(int x, int y) {
       tree[num].v = y;    tree[num].next = head[x];    head[x] = num++;}void dfs(int u) {
       vis[u] = 1;    dp[u] = 1;    for (int i = head[u]; i != -1; i = tree[i].next) {
           int v = tree[i].v;        if (!vis[v]) {
               dfs(v);            dp[u] += dp[v];        }    }    // 要选k个点，这条边连接的两个连通块大小为x，y的话，贡献为C(n,k)-C(x,k)-C(y,k)    answer = (answer + cbk[n] - cbk[dp[u]] - cbk[n - dp[u]] + 2 * mod) % mod;}int main() {
       cin >> n >> k;    memset(head, -1, sizeof(head));    memset(vis, 0, sizeof(vis));    for (int i = 1; i < n; i++) {
           int a, b;        cin >> a >> b;        add(a, b);        add(b, a);    }    cbk[k] = 1;    for (int i = k + 1; i <= n; i++) {
           cbk[i] = ((cbk[i - 1] * i) % mod * getInv(i - k)) % mod;    }    dfs(1);    cout << answer << endl;    return 0;}
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/111665971 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！