容斥
按照套路，按边考虑。一条边能贡献的答案是选的k个点分居两侧的方案数。发现这东西很难求。于是转成容斥求k个点归于一侧的方案数。
#include<cstdio>#define N 100005#define MOD 1000000007using namespace std;namespace runzhe2000{ typedef long long ll; int fac[N], inv[N], inc[N], last[N], ecnt, ans, tot, n, k; struct edge{int next, to;}e[N<<1]; void addedge(int a, int b) { e[++ecnt] = (edge){last[a], b}; last[a] = ecnt; } int C(int x, int y) { if(x < y) return 0; return (ll) fac[x] * inc[y] % MOD * inc[x-y] % MOD; } int dfs(int x, int f) { int siz = 1; for(int i = last[x]; i; i = e[i].next) { int y = e[i].to; if(y == f) continue; siz += dfs(y, x); } (ans += ((tot - C(siz, k)) % MOD - C(n-siz, k)) % MOD) %= MOD; return siz; } void main() { scanf("%d%d",&n,&k); for(int i = 1; i < n; i++) { int x, y; scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } fac[0] = fac[1] = inv[1] = inc[0] = inc[1] = 1; for(int i = 2; i <= n; i++) { fac[i] = (ll)fac[i-1]*i%MOD; inv[i] = (ll)(MOD-MOD/i)*inv[MOD%i]%MOD; inc[i] = (ll)inc[i-1]*inv[i]%MOD; } tot = C(n,k); dfs(1,0); PRintf("%d/n",(ans+MOD)%MOD); }}int main(){ runzhe2000::main();}新闻热点
疑难解答
