HDU 4705 Y 树形枚举

树形枚举--搜索

题目描述：

给你一棵树，要在一条简单路径上选3个不同的点构成一个集合，问能构成多少个不同的集合。

解法：

枚举所有结点，假设某个结点有n棵子树，每棵子树的结点个数分别为s1,s2,````sn.那么在选中该结点后，剩下的两个结点从子树上选，考虑顺序，则有方案数ans = s1*(sum(si) - s1) + s2*(sum(si) - s2) + ``` + sn*(sum(si) - sn),化简得ans = sum(si) ^ 2 - sum(si ^2) .实际上，另外两个点选了(1,2)和(2,1)对于集合{a,b,c}而言是一样的，所以方案数应该为ans/2。

而一个结点的子节点的总和为n-1。只要求sum(si^2)即可，由于是从某一点开始搜的，我们把这个点想成了根结点，实际上对于除这个点以外的其他点，除了按搜索顺序认为的子树外，剩下的结点是它的另一棵子树。

代码实现：

ll ans=0;

int dfs(int x)//返回该结点的某棵子树的结点个数

{

vis[x] =1;

ll sq=0;//”子树”结点个数的平方和

int tot =0;//”子树”结点个数的总和

for(int i=0; i<g[x].size(); ++i)

{

if(!vis[g[x][i]])

{

int son = dfs(g[x][i]);//子结点的个数

tot += son;

sq += (ll)son*son;

}

sq += (ll)(n-tot-1)*(n-tot-1);

ans += ((ll)(n-1)*(n-1) - sq)/2;

return tot+1;//当自己作为子树时，还要加上自己，所以加1.

}

另一种解法：

直接考虑顺序计数,有方案数ans =s1*(s2+s3+````+sn)+s2*(s3+s4+```sn) +```` + s[n-1]*sn. 则有设sum[i]为前i项和，则有ans = s1*(n-1-sum[1]) + s2*(n-1-sum[2]) +````+s[n-1]*(n-1-sum[n-1]) + sn *0.

代码实现：

ll ans;

int dfs(int x)

{

vis[x] =1;

int tmp=0;

for(int i=0; i<g[x].size(); ++i)

{

if(!vis[g[x][i]])

{

int son = dfs(g[x][i]);//当前分支的儿子个数

tmp += son;//已经求出的儿子个数，相当于sum[i]

ans += (ll)(n-1-tmp)*son;

}

return tmp+1;

}

然后此题的正解就是C(n,3)- ans.C(n,3)表示从n个点中选3个点，C(n,3) = n*(n-1)*(n-2)/6

贴代码1：

 1 #pragma comment(linker, "/STACK:16777216")
 2 #include<cstdio>
 3 #include<vector>
 4 #define N 100010
 5 using namespace std;
 6 typedef long long int ll;
 7 vector<int> g[N];
 8 bool vis[N];
 9 int n;
10 ll ans;
11 int dfs(int x)
12 {
13     vis[x] =1;
14     ll sq=0;//子节点个数的平方和
15     int tot =0;//子节点个数之和
16     for(int i=0; i<g[x].size(); ++i)
17     {
18         if(!vis[g[x][i]])
19         {
20             int son = dfs(g[x][i]);//子节点的个数
21             tot += son;
22             sq += (ll)son*son;
23         }
24     }
25     sq += (ll)(n-tot-1)*(n-tot-1);
26     ans += ((ll)(n-1)*(n-1) - sq)/2;
27     return tot+1;
28 }
29 int main()
30 {
31     freopen("1010.in","r",stdin);
32     while(~scanf("%d",&n))
33     {
34         for(int i=1; i<=n; ++i)
35         {
36             g[i].clear();
37             vis[i] =0;
38         }
39         for(int i=1; i<n; ++i)
40         {
41             int u,v;
42             scanf("%d%d",&u,&v);
43             g[u].push_back(v);
44             g[v].push_back(u);
45         }
46         ans =0;
47         dfs(1);
48         ll sum = (ll)n*(n-1)*(n-2)/6;
49         printf("%I64d
",sum-ans);
50     }
51     return 0;
52 }

View Code

贴代码2：

 1 #pragma comment(linker, "/STACK:16777216")
 2 #include<cstdio>
 3 #include<vector>
 4 #define N 100010
 5 using namespace std;
 6 typedef long long int ll;
 7 vector<int> g[N];
 8 bool vis[N];
 9 int n;
10 ll ans;
11 int dfs(int x)
12 {
13     vis[x] =1;
14     int tmp=0;
15     for(int i=0; i<g[x].size(); ++i)
16     {
17         if(!vis[g[x][i]])
18         {
19             int son = dfs(g[x][i]);//当前分支的儿子个数
20             tmp += son;//已经求出的儿子个数
21             ans += (ll)(n-1-tmp)*son;
22         }
23     }
24     return tmp+1;
25 }
26 int main()
27 {
28 //    freopen("1010.in","r",stdin);
29     while(~scanf("%d",&n))
30     {
31         for(int i=1; i<=n; ++i)
32         {
33             g[i].clear();
34             vis[i] =0;
35         }
36         for(int i=1; i<n; ++i)
37         {
38             int u,v;
39             scanf("%d%d",&u,&v);
40             g[u].push_back(v);
41             g[v].push_back(u);
42         }
43         ans =0;
44         dfs(1);
45         ll sum = (ll)n*(n-1)*(n-2)/6;
46         printf("%I64d
",sum-ans);
47     }
48     return 0;
49 }

View Code