HDU-4705 Y(思维+dfs树)
程序员文章站
2022-04-14 15:35:07
Input Output 题意:给你一颗树,选择一个三个点构成的集合,使得这三个点不在一条直线上(意思就是 从一个点出发,用一条不回头的线不能将这三个点连起来)问一共有多少个这样的集合 思路 :先求出一共有多少个集合,就是Cn3 (n-2)*(n-1)*n/6 ; 然后再求不符合条件的个数 求不符合 ......
input
4 1 2 1 3 1 4
output
1
题意:给你一颗树,选择一个三个点构成的集合,使得这三个点不在一条直线上(意思就是 从一个点出发,用一条不回头的线不能将这三个点连起来)问一共有多少个这样的集合
思路 :先求出一共有多少个集合,就是cn3 (n-2)*(n-1)*n/6 ; 然后再求不符合条件的个数
求不符合条件的集合时 比如上图:先以2为中心然后在3中选一个,在4,5,1,6,7,8,9中选一个种类数就是1×7
然后在4中选一个,在5,1,6,7,8,9中选一个种类数是1×6;
依此递归求解;
代码如下:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdio> 4 #include <vector> 5 #include <algorithm> 6 #include <cstring> 7 using namespace std; 8 typedef long long ll; 9 const int maxn=1e6+5; 10 ll n; 11 ll sizes[maxn],ans; 12 vector<int> v[maxn]; 13 ll cal(ll n,ll m) 14 { 15 return n*(n-1)*(n-2)/6; 16 } 17 void dfs(int x,int fa) 18 { 19 sizes[x]=1; 20 for(int i=0;i<v[x].size();i++) 21 { 22 int y=v[x][i]; 23 if(y!=fa) 24 { 25 dfs(y,x); 26 sizes[x]+=sizes[y]; 27 ans+=(sizes[y]*(n-sizes[x])); 28 } 30 } 31 } 32 int main() 33 { 34 int t; 35 36 while(~scanf("%lld",&n)) 37 { 38 ans=0; 39 memset(sizes,0,sizeof(sizes)); 40 for(int i=1;i<=n;i++)v[i].clear(); 41 for(int i=1;i<n;i++) 42 { 43 int l,k; 44 scanf("%d%d",&l,&k); 45 v[k].push_back(l); 46 v[l].push_back(k); 47 } 48 dfs(1,-1); 49 printf("%lld\n",cal(n,3)-ans); 50 } 51 52 53 return 0; 54 }
下一篇: 带着萌新看springboot源码06