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;
}

最后

以上就是有魅力蜡烛为你收集整理的HDU 4705 Y的全部内容，希望文章能够帮你解决HDU 4705 Y所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。