1 /* 2 题目大意：给一棵n个节点的树，求任意三个点两两无直系亲属关系的种数。 3 可以求反方向的，对于每个节点i使他选,他的一个子树中选一个，再在剩余的任意选一个。 4 */ 5 #pragma comment(linker, "/STACK:16777216") 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <vector>10 using namespace std;11 12 const int maxn=100005;13 typedef __int64 LL;14 int num[maxn],n;LL ans;15 vector<int>f[maxn];16 17 void dfs(int u,int pre)18 {19     num[u]=1;20     for(int i=0;i<f[u].size();i++)21     {22         int v=f[u][i];23         if(v==pre) continue;24         dfs(v,u);25         num[u]+=num[v];26         ans+=(LL)num[v]*(n-num[u]);    27     }28     return ;29 }30 int main()31 {32     int i,a,b;33     while(~scanf("%d",&n))34     {35         for(i=1;i<=n;i++) f[i].clear();36         for(i=1;i<n;i++)37         {38             scanf("%d%d",&a,&b);39             f[a].push_back(b);40             f[b].push_back(a);41         }42         memset(num,0,sizeof(num));43         ans=0;44         dfs(1,-1);45         printf("%I64d\n",(LL)n*(n-1)*(n-2)/6-ans);46     }47     return 0;48 }