学步园

给一棵树求有多少三个点之间没有简单路径，简单路径就是不走重复的点，小boss给我说了想法之后，写出来错了，不是自己想出来的方法还是有点不熟，就画图自己找，给的想法大方向上已经对了，总共有C(n,3)种组合，只要求出有简单路径的组合数就ok了，任意一点u为中间点，在当前求得的儿子son中选一个，u，剩下所有的节点n-temp-1(temp为已经求出的u的儿子个数，儿子跟儿子间不能重复运算)中选一个，可以组成有son*（n-temp-1）种组合，

#pragma comment(linker, "/STACK:1024000000,1024000000")    
#include<stdio.h>
#include<string.h>
int vis[100010],head[100010],num,n;
__int64 ans;
struct edge
{
    int st,ed,next;
}e[200010];
void addedge(int x,int y)
{
    e[num].st=x;e[num].ed=y;e[num].next=head[x];head[x]=num++;
    e[num].st=y;e[num].ed=x;e[num].next=head[y];head[y]=num++;
}
int dfs(int u)
{
	int i,v,temp=0,f;
    vis[u]=1;   
    for(i=head[u];i!=-1;i=e[i].next)
    {
        v=e[i].ed;
        if(vis[v]==1)continue;
        f=dfs(v);//当前分支儿子的个数
		temp+=f;//已经求出的儿子个数
		ans+=(__int64)(n-temp-1)*(__int64)f;//组合数
    }
    return temp+1;
}
int main()
{
    int x,y,i;
    __int64 sum,a;
    while(scanf("%d",&n)!=-1)
    {
        memset(head,-1,sizeof(head));
        num=0;ans=0;
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            addedge(x,y);
        }
        memset(vis,0,sizeof(vis));
        dfs(1);
        a=n;
        sum=a*(a-1)*(a-2)/6;
        printf("%I64d\n",sum-ans);
    }
    return 0;
}