Y

 1 # include <bits/stdc++.h> 2 #pragma comment(linker, "/STACK:1024000000,1024000000") 3 using namespace std; 4  5 const int MAX = 100010; 6 typedef long long int ll; 7 struct node 8 { 9     int to;10     int next;11 }tree[MAX * 2];12 int head[MAX], num[MAX];13 int tol = 0;14 int n;15 ll sum;16 void add(int a, int b)17 {18     tree[tol].to = b;19     tree[tol].next = head[a];20     head[a] = tol++;21 }22 23 void dfs(int root, int f)24 {25     num[root] = 1;26     int tep = 0;27     for(int i = head[root]; i != -1; i = tree[i].next)28     {29         int son = tree[i].to;30         if(son == f)31             continue;32         dfs(son, root);33         34         sum += (ll) tep * num[son];35         num[root] += num[son];36         tep += num[son];37     }38     sum += (ll) tep * (n - num[root]);39 }40 41 int main()42 {43     while(scanf("%d", &n) != EOF)44     {45         tol = 0;46         sum = 0;47         memset(head, -1, sizeof(head));48         49         int a, b;50         for(int i = 1; i < n; i++)51         {52             scanf("%d%d", &a, &b);53             add(a, b);54             add(b, a);55         }56         dfs(1, -1);57         ll all = (ll)n * (n - 1) * (n - 2) / 6;58         59         printf("%I64d\n", all - sum);60     }61     return 0;62 }