51Nod - 1677树形dp + 组合数学

题意：

给定一棵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示例 3 2 1 2 1 3 Output示例 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; }