HDU 4705 Y

Y

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 209 Accepted Submission(s): 69

Problem Description

Sample Input

Sample Output

1
Hint

1. The only set is {2,3,4}.

2. Please use #pragma comment(linker, "/STACK:16777216")

Source

2013 Multi-University Training Contest 10

多校第十场，也是最后一场了，我们弱弱地过了两题，这题是我过的

对所给的树，随意选一个结点做为根节点，这里我选了标号为1的节点，然后作一遍DFS，求出每个节点的子孙节点个数（包含这个节点本身）。

之后对每一个节点，求出以它为Simple Path中间那个节点时的简单路条数，这里的求法是这样的：

　　对于每个节点，我们DFS之后就可以知道与它相连的每棵子树的节点个数（包括它连向父节点的那棵子树），设这些子树的节点个数分别为k1，k2，k3……kn

　　则以这个节点为中间节点形成的简单路条数为k1*k2+k1*k3+k1*k4+……+k1*kn+k2*k3+k2*k4+……+kn-1*kn

　　将此式乘2后可化为：k1*(k2+k3+……+kn)+k2*(k1+k3+……+kn)+……+kn*(k1+k2+k3+……+kn-1)

　　　　　　　　　　=k1*(n-1-k1)+k2*(n-1-k2)+k3*(n-1-k3)+……+kn*(n-1-kn)

　　　　　　　　　　=(n-1)*(k1+k2+……+kn)-k1^2-k2^2-……-kn^2

　　　　　　　　　　=(n-1)^2-k1^2-k2^2-……-kn^2

由上式可求得所有的Simple Path数目，则所有的非Simple Path数目就是C³_n - Simple Path

另外注意此题在HDU上提交要手动扩栈，并必须用C++提交，G++是不提供扩栈的

 1 #pragma comment(linker, "/STACK:16777216")
 2 
 3 #include<iostream>
 4 #include<vector>
 5 #include<cstdio>
 6 #include<cstring>
 7 
 8 using namespace std;
 9 
10 int n;
11 int node[100050];
12 vector<int> tree[100050];
13 vector<int> tree_2[100050];
14 long long result;
15 
16 int dfs_1(int a,int pre)
17 {
18     if(node[a])
19         return node[a];
20     int ans=1;
21     int e=tree[a].size();
22     for(int i=0;i<e;i++)
23         if(tree[a][i]!=pre)
24         {
25             ans+=dfs_1(tree[a][i],a);
26             tree_2[a].push_back(node[tree[a][i]]);
27         }
28     node[a]=ans;
29     tree_2[a].push_back(n-node[a]);
30     if(e>1)//求得子节点个数后,可顺便求出过该节点的Sample Path数
31     {
32         long long temp=(long long)(n-1)*(n-1);
33         for(int i=0;i<e;i++)
34             temp-=(long long)tree_2[a][i]*tree_2[a][i];
35         result+=temp/2;
36     }
37     return node[a];
38 }
39 
40 int main()
41 {
42     while(scanf("%d",&n)==1)
43     {
44         result=0;
45         memset(node,0,sizeof(int)*(n+1));
46         for(int i=1;i<=n;i++)
47         {
48             tree[i].clear();
49             tree_2[i].clear();
50         }
51         for(int i=1;i<n;i++)
52         {
53             int a,b;
54             scanf("%d %d",&a,&b);
55             tree[a].push_back(b);
56             tree[b].push_back(a);
57         }
58         dfs_1(1,-1);
59         result=(long long)n*(n-1)*(n-2)/6-result;
60         printf("%I64d
",result);
61     }
62 
63     return 0;
64 }

[C++]