#include <bits/stdc++.h> using namespace std; const int MX=100100; int n,i,cur,now,xc,yc,it,x[MX],y[MX],k[MX],nx[MX],ny[MX],w[MX],cnt[MX],p[MX],rk[MX],is[MX],s[MX],sit[MX]; vector<int> g[MX]; long long r; void ofs(int i, int p, int mxs) { for (int j=n; j>0; j&=j-1) if (sit[j]==it) r+=s[j]; for (int j=mxs-i-1; j>0; j&=j-1) if (sit[j]==it) r-=s[j]; for (int j=0; j<g[i].size(); j++) { int k=g[i][j]; if (k==p) continue; ofs(k,i,mxs); } } void ins(int i) { if (is[i]==it) return; is[i]=it; for (; i<=n; i=(i<<1)-(i&(i-1))) if (sit[i]!=it) { sit[i]=it; s[i]=1; } else s[i]++; } void dfs(int cur) { if (nx[cur]!=0) { ++it; dfs(nx[cur]); ins(x[cur]); } if (ny[cur]!=0) { ++it; dfs(ny[cur]); } ins(y[cur]); ofs(x[cur],y[cur],x[cur]+y[cur]); ins(x[cur]); } bool cmp(int i, int j) { return x[i]+y[i]<x[j]+y[j]; } int fs(int x) { if (x!=p[x]) p[x]=fs(p[x]); return p[x]; } int main() { scanf("%d",&n); for (i=1; i<n; i++) { scanf("%d%d",&x[i],&y[i]); g[x[i]].push_back(y[i]); g[y[i]].push_back(x[i]); k[i-1]=i; } if (n==1) { puts("0"); return 0; } for (i=1; i<=n; i++) p[i]=i; sort(k,k+n-1,cmp); ++it; for (i=0; i<n-1; i++) { cur=k[i]; xc=fs(x[cur]); yc=fs(y[cur]); if (xc==yc) continue; if (rk[yc]>=rk[xc]) { p[xc]=now=yc; if (rk[yc]==rk[xc]) rk[yc]++; } else p[yc]=now=xc; if (cnt[w[yc]]>=cnt[w[xc]]) { nx[cur]=w[xc]; ny[cur]=w[yc]; } else { nx[cur]=w[yc]; ny[cur]=w[xc]; swap(x[cur],y[cur]); } cnt[cur]=cnt[w[xc]]+cnt[w[yc]]+1; w[now]=cur; } dfs(cur); printf("%lld\n",r); return 0; }