【计数】51nod1677 treecnt

要将答案看做是小问题的贡献和

Description

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

现需要计算对于所有选择k个点的情况最小选择边数的总和为多少。
样例解释：

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

选择点{1,2}:至少要选择第一条边使得1和2联通。

选择点{1,3}:至少要选择第二条边使得1和3联通。

选择点{2,3}:两条边都要选择才能使2和3联通。

Input

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

接下来n-1行，每行两个数x,y描述一条边(1<=x,y<=n)

Output

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

Input示例

Output示例

题目分析

初看上去好像要结合树形结构做一些麻烦的事情……例如判断树中长度为k的连通块个数之类的。

但是实际上问题可以看做是每一条边对于答案贡献了$si$，答案就是$\sum{si}$。

那么单独的贡献自然应该是选择了横跨这条边的两个点的情况。

这里就考虑一下问题的反面：选择了不横跨这条边的情况，应该是$C_{u_{size}}^{k}+C_{v_{size}}^{k}$，其中$u_{size}$和$v_{size}$分别表示这条边两边有多少个点。

于是就愉快地解决这题了。

 #include<bits/stdc++.h>

 typedef long long ll;

 const ll MO = ;

 const int maxn = ;

 const int maxm = ;

 ll fac[maxn],facinv[maxn],ans,sum;

 int n,k;

 int size[maxn];

 int edges[maxm],nxt[maxm],head[maxn],edgeTot;

 int read()

 {

     char ch = getchar();

     int num = ;

     bool fl = ;

     for (; !isdigit(ch); ch = getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch = getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 void addedge(int u, int v)

 {

     edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;

     edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot;

 }

 void dfs1(int x, int fa)

 {

     size[x] = ;

     for (int i=head[x]; i!=-; i=nxt[i])

         if (edges[i]!=fa) dfs1(edges[i], x), size[x] += size[edges[i]];

 }

 ll c(ll n, ll m){return n < m?:fac[n]*facinv[n-m]%MO*facinv[m]%MO;}

 void dfs2(int x, int fa)

 {

     for (int i=head[x]; i!=-; i=nxt[i])

     {

         int v = edges[i];

         if (fa==v) continue;

         ans = (ans+sum-c(size[v], k)-c(n-size[v], k))%MO;

         dfs2(v, x);

     }

 }

 int main()

 {

     memset(head, -, sizeof head);

     n = read(), k = read(), fac[] = facinv[] = facinv[] = ;

     for (int i=; i<n; i++) addedge(read(), read());

     for (int i=; i<=n; i++) facinv[i] = (MO-MO/i)*facinv[MO%i]%MO;

     for (int i=; i<=n; i++)

        fac[i] = (fac[i-]*i)%MO, facinv[i] = facinv[i]*facinv[i-]%MO;

     sum = c(n, k);

     dfs1(, );

     dfs2(, );

     printf("%lld\n",(ans+MO)%MO);

     return ;

 }

END

巴特西