hdu 4705 Y

dfs

1.要#pragma comment(linker, "/STACK:16777216")

2.扩栈要 vc++编译环境

3.不能用%lld，要用%I64d，无语。。

#pragma comment(linker, "/STACK:16777216")//手动扩栈
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;

const int MAXN = 1e5+10;
#define LL long long
vector<int> q[MAXN];
int f[MAXN];
LL ans;
int n;

int dfs(int u)
{
	int i,j,temp,sum=0;
	f[u]=1;
	for(i=0;i<q[u].size();i++){
		int v=q[u][i];
		if(!f[v]) {
			temp=dfs(v);
			sum+=temp;
			ans+=(LL)temp*(n-1-temp);
		}
	}
	ans+=(LL)sum*(n-1-sum);
	sum++;
	return sum;
}
int main()
{
	int i,j,k;
	while(scanf("%d",&n)!=EOF){
		int a,b;
		for(i=1;i<=n;i++){
			q[i].clear();
			f[i]=0;
		}
		ans=0;
		for(i=1;i<n;i++)
		{
			scanf("%d%d",&a,&b);
			q[a].push_back(b);
			q[b].push_back(a);
		}
		dfs(1);
		LL t=(LL)n*(n-1)*(n-2)/6;
		printf("%I64d\n",t-ans/2);//用%lld竟然wa。。。
	}
}