首页 > 代码库 > treecnt 算法马拉松20（告别美国大选及卡斯特罗）
treecnt 算法马拉松20（告别美国大选及卡斯特罗）
treecnt
基准时间限制：1 秒 空间限制：131072 KB
给定一棵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 21 21 3
Output示例
4
思路：考虑每一条边的贡献。
一条边把一棵树分成两部分，当这条边有贡献时，k个点必然分布在这条边分隔开的两部分。
总情况数等于C（n,k）,设其中一部分点数为x，另一部分则为n-x，不合法情况数等于C（x,k）+C(n-x,k);然后要解决的就是咋去
找一条边两边点的个数，那么我们以某个点为根dfs找出各个点的子树的度，然后遍历每条边，那么当前两个点，度小的必然为另一个的子树，那么x就找出来了。
复杂度O(n);
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<math.h> 6 #include<queue> 7 #include<stdlib.h> 8 #include<set> 9 #include<vector> 10 typedef long long LL; 11 using namespace std; 12 typedef struct node 13 { 14 int x; 15 int y; 16 } ss; 17 ss ans[100005]; 18 vector<int>vec[100005]; 19 int cnt[100005]; 20 bool flag[100005]; 21 int dfs(int n); 22 LL N[100005]; 23 const LL mod = 1e9+7; 24 LL quick(LL n,LL m); 25 int main(void) 26 { 27 int n,k,i; 28 N[0] = 1; 29 for(i = 1; i <= 100000; i++) 30 { 31 N[i] = N[i-1]*(LL)i%mod; 32 } 33 while(scanf("%d %d",&n,&k)!=EOF) 34 { 35 // int i; 36 memset(cnt,0,sizeof(cnt)); 37 memset(flag,0,sizeof(flag)); 38 for(i = 0; i <= n; i++) 39 vec[i].clear(); 40 for(i = 0; i < n-1; i++) 41 { 42 scanf("%d %d",&ans[i].x,&ans[i].y); 43 vec[ans[i].x].push_back(ans[i].y); 44 vec[ans[i].y].push_back(ans[i].x); 45 } 46 dfs(1); 47 LL ni = N[n-k]*N[k]%mod; 48 ni = quick(ni,mod-2); 49 LL sum = N[n]*ni%mod; 50 sum = sum*(n-1)%mod; 51 for(i = 0; i < n-1; i++) 52 { 53 int x = cnt[ans[i].x]; 54 int y = cnt[ans[i].y]; 55 int aa = min(x,y); 56 int bb = n-aa; 57 if(aa >= k) 58 { 59 LL xx = N[aa-k]*N[k]%mod; 60 ni = quick(xx,mod-2); 61 ni = N[aa]*ni%mod; 62 sum = sum - ni; 63 sum = (sum%mod)+mod; 64 sum%=mod; 65 } 66 if(bb >= k) 67 { 68 LL xx = N[bb-k]*N[k]%mod; 69 ni = quick(xx,mod-2); 70 ni = N[bb]*ni%mod; //printf("%lld\n",ni); 71 sum = sum - ni; 72 sum = (sum%mod)+mod; 73 sum%=mod; 74 } 75 } 76 printf("%lld\n",sum); 77 } 78 } 79 int dfs(int n) 80 { 81 flag[n] = true; 82 int i; 83 for(i = 0; i < vec[n].size(); i++) 84 { 85 int x = vec[n][i]; 86 if(!flag[x]) 87 { 88 cnt[n]+=dfs(x); 89 } 90 } 91 cnt[n]++; 92 return cnt[n]; 93 } 94 LL quick(LL n,LL m) 95 { 96 LL ask = 1; 97 n%=mod; 98 while(m) 99 {100 if(m&1)101 ask = ask*n%mod;102 n = n*n%mod;103 m>>=1;104 }105 return ask;106 }
treecnt 算法马拉松20（告别美国大选及卡斯特罗）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。