HDU-4705 Y（思維+dfs樹）

Input

4
1 2
1 3
1 4

Output

1

題意：給你一顆樹，選擇一個三個點構成的集合，使得這三個點不在一條直線上（意思就是 從一個點出發，用一條不回頭的線不能將這三個點連起來）問一共有多少個這樣的集合

思路 ：先求出一共有多少個集合，就是C_{n^{3    （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 }