HDU - 4705 Y

题解：求出在一条线的三个点，然后全部的三种情况减去就可以了，怎么会出现在一条线呢，假设A节点必选，那么对于某一分支选一个，其他所有点选一个，意思就是枚举一条线中 三个点的中点 两边分别选一个就可以了。不要用 lld，用 I64d 前几天交上之后不能判，信心满满会过，就没管，今天看没过的题发现有他.....

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,son[N];
ll C[N][5],ans;
vector<int> v[N];
void init()
{
	C[0][0]=C[1][0]=C[1][1]=1;
	for(int i=2;i<=1e5;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=3;j++)
			C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
}
void dfs(int fa,int u)
{
	son[u]=1;
	for(int i=0;i<v[u].size();i++)
	{
		int to=v[u][i];
		if(to==fa) continue;
		dfs(u,to);
		son[u]+=son[to];
		ans+=(ll)(n-son[u])*son[to];
	}
}
int main()
{
	init();
	int x,y;
	while(~scanf("%d",&n))
	{
		ans=0;
		for(int i=1;i<=n;i++) v[i].clear();
		for(int i=1;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			v[x].push_back(y);
			v[y].push_back(x);
		}
		dfs(0,1);
		printf("%I64d\n",C[n][3]-ans);
	}
	return 0;
}