51NOD 1677 treecnt

treecnt
基準時間限制： 秒 空間限制： KB 分值:  難度：級算法題 收藏  關注
給定一棵n個節點的樹，從到n标号。選擇k個點，你需要選擇一些邊使得這k個點通過選擇的邊聯通，目标是使得選擇的邊數最少。
現需要計算對于所有選擇k個點的情況最小選擇邊數的總和為多少。
樣例解釋：

一共有三種可能:(下列配圖藍色點表示選擇的點，紅色邊表示最優方案中的邊)
選擇點{1,2}:至少要選擇第一條邊使得和聯通。

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


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



Input
第一行兩個數n，k(<=k<=n<=)
接下來n-行，每行兩個數x,y描述一條邊(<=x,y<=n)
Output
一個數，答案對,,,取模。
Input示例
 
 
 
Output示例

           

對任意邊(u,v)

設a=以v為根的子樹的點

b=n-a

那這條邊被選擇的次數=C(a,1)*C(b,k-1)+C(a,2)*C(b,k-2)+C(a,3)*C(b,k-3)+…..

顯然 這樣肯定會TLE

不妨換個角度

考慮從n個點中選擇k個點 一共有C(n,k)總情況

當k個點全在a中選出來 或 k個點全在b中選出來的情況是要排除的

是以這條邊被選擇的次數為C(n,k)-C(a,k)-C(b,k)

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<time.h>
#include<math.h>
#include<list>
#include<cstring>
#include<fstream>
//#include<memory.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define INF 1000000007
#define pll pair<ll,ll>
#define pid pair<int,double>

const int N=+;

int head[N];
struct Edge{
    int to,next;
    int num;
}edge[*N];

inline void addEdge(int k,int u,int v){
    edge[k].to=v;
    edge[k].next=head[u];
    head[u]=k;
}

ll egcd(ll a,ll b,ll&x,ll&y){
    if(b==){
        x=,y=;
        return a;
    }
    else{
        ll d=egcd(b,a%b,x,y);
        ll xt=x,yt=y;
        x=yt;
        y=xt-a/b*yt;
        return d;
    }
}

ll fac[N];

inline ll C(int n,int k){
    if(n==k)
        return ;
    if(n<k)
        return ;
    ll x,y;
    ll fz=fac[n];
    ll fm=(fac[k]*fac[n-k])%INF;
    egcd(fm,INF,x,y);
    x=(x+INF)%INF;
    ll ans=(fz*x)%INF;
    return ans;
}

void init(int n){
    fill(head,head+n+,-);
    fac[]=;
    for(int i=;i<=n;++i){
        fac[i]=(fac[i-]*i)%INF;
    }
}

inline int dfs(int u,int father){
    int sum=;
    for(int i=head[u];i!=-;i=edge[i].next){
        int v=edge[i].to;
        if(v==father)
            continue;
        int num=dfs(v,u);
        edge[i].num=edge[i^].num=num;
        sum+=num;
    }
    return sum;
}

ll slove(int n,int k){
    ll sum=C(n,k);
    dfs(,-);
    ll ans=;
    for(int i=;i<*(n-);i+=){
        int a=edge[i].num;
        int b=n-a;
        ll tmp=sum-C(a,k)-C(b,k);
        ans=(ans+tmp)%INF;
    }
    return (ans+INF)%INF;
}

int main()
{
    //freopen("/home/lu/文檔/r.txt","r",stdin);
    //freopen("/home/lu/文檔/w.txt","w",stdout);
    int n,k;
    scanf("%d%d",&n,&k);
    init(n);
    for(int i=,u,v;i<n-;++i){
        scanf("%d%d",&u,&v);
        addEdge(*i,u,v);
        addEdge(*i+,v,u);
    }
    printf("%lld\n",slove(n,k));
    return ;
}