HDU 4705 Y

74 阅读 0 评论 49 点赞

我是靠谱客的博主有魅力蜡烛，这篇文章主要介绍HDU 4705 Y，现在分享给大家，希望可以做个参考。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4705

解析：要求三个不在同一路径的，我们可以先求出在同一路径的三个有多少种，然后减去就行了。

用dfs来遍历所有点，对于当前点node，研究它的每个分支p。三个点，node算一个，node的当前分支p里任取一个点，然后在不是p的地方在找一个。

注意：

1.需要手动扩栈 #pragma comment(linker, "/STACK:16777216")

2.long long的变量输入数去用%I64d,不要用%lld

3.强制类型转换的时候不要加括号

复制代码

#pragma comment(linker, "/STACK:16777216")//手动扩栈

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"vector"
using namespace std;
#define LL long long
#define Maxnode 100005

int N;
vector<int>graph[Maxnode];
int flag[Maxnode];		//标记是否遍历过此点
LL ans ;				//用来存储在同一条路径上的三个点的个数

int DFS(int node){
	int child_node = 0;
	flag[node] = 1;
	for(int i = 0 ; i < graph[node].size() ; i++){
		int v = graph[node][i];
		if(!flag[v]){  
			int temp = DFS(v);
			child_node += temp;
			ans += (LL)(N - 1 - child_node)*temp; 
			//关键步骤，计算每个节点的分支之间共有多少个同一路径的
		}
	}
	//child_node++; //加上自己
	return child_node+1;
}

int main(){
	while(scanf("%d",&N) != EOF){
		ans = 0;
		memset(flag,0,sizeof(flag));
		for(int i = 1; i <= N ; i++)
			graph[i].clear();
		int a,b;
		for(int i = 1; i <= N-1; i ++){
			scanf("%d%d",&a,&b);
			graph[a].push_back(b);
			graph[b].push_back(a);
		}
		DFS(1);
		LL sum = (LL)N*(N-1)*(N-2)/6; //N个节点中取3个
		//注意，不能变成（(LL)N*(N-1)*(N-2)/6），会溢出的
		printf("%I64dn",sum-ans);
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#pragma comment(linker, "/STACK:16777216")//手动扩栈

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"vector"
using namespace std;
#define LL long long
#define Maxnode 100005

int N;
vector<int>graph[Maxnode];
int flag[Maxnode];		//标记是否遍历过此点
LL ans ;				//用来存储在同一条路径上的三个点的个数

int DFS(int node){
	int child_node = 0;
	flag[node] = 1;
	for(int i = 0 ; i < graph[node].size() ; i++){
		int v = graph[node][i];
		if(!flag[v]){  
			int temp = DFS(v);
			child_node += temp;
			ans += (LL)(N - 1 - child_node)*temp; 
			//关键步骤，计算每个节点的分支之间共有多少个同一路径的
		}
	}
	//child_node++; //加上自己
	return child_node+1;
}

int main(){
	while(scanf("%d",&N) != EOF){
		ans = 0;
		memset(flag,0,sizeof(flag));
		for(int i = 1; i <= N ; i++)
			graph[i].clear();
		int a,b;
		for(int i = 1; i <= N-1; i ++){
			scanf("%d%d",&a,&b);
			graph[a].push_back(b);
			graph[b].push_back(a);
		}
		DFS(1);
		LL sum = (LL)N*(N-1)*(N-2)/6; //N个节点中取3个
		//注意，不能变成（(LL)N*(N-1)*(N-2)/6），会溢出的
		printf("%I64dn",sum-ans);
	}
	return 0;
}