#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=2e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,dep[maxn]; int dfn[maxn],top[maxn],siz[maxn],son[maxn],fa[maxn],idfn[maxn],cnt; vector<int>E[maxn]; void link(int x,int y){ E[x].p_b(y),E[y].p_b(x); } void dfs(int u,int fa){ dep[u]=dep[fa]+1,::fa[u]=fa,siz[u]=1; for(int x:E[u])if(x!=fa)dfs(x,u),siz[u]+=siz[x],son[u]=(siz[x]>siz[son[u]])?x:son[u]; } void dfs2(int u,int tp){ top[u]=tp,idfn[dfn[u]=++cnt]=u; if(!son[u])return;dfs2(son[u],tp); for(int x:E[u])if(x!=fa[u]&&x!=son[u])dfs2(x,x); } struct SegTree { struct nd { ll lz,sm,len; void push(ll k){lz+=k,sm+=len*k;} }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) void pd(int p){d[ls(p)].push(d[p].lz),d[rs(p)].push(d[p].lz),d[p].lz=0;} void pu(int p){d[p].sm=d[ls(p)].sm+d[rs(p)].sm;} void bd(int l,int r,int p){ d[p].len=r-l+1; if(l==r)return; int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p)); } void modify(int l,int r,int s,int t,int p,int x){ if(l<=s&&t<=r)return d[p].push(x);pd(p); int mid=s+t>>1; if(l<=mid)modify(l,r,s,mid,ls(p),x);if(r>mid)modify(l,r,mid+1,t,rs(p),x);pu(p); } ll ask(int l,int r,int s,int t,int p){ if(l<=s&&t<=r)return d[p].sm;pd(p); int mid=s+t>>1;ll res=0; if(l<=mid)res+=ask(l,r,s,mid,ls(p));if(r>mid)res+=ask(l,r,mid+1,t,rs(p)); return res; } }T; int lca(int x,int y){ while(top[x]!=top[y])if(dep[top[x]]>=dep[top[y]])x=fa[top[x]];else y=fa[top[y]]; return dep[x]<dep[y]?x:y; } int ask_kth(int x,int k){ while(k){ if(k>dep[x]-dep[top[x]])k-=dep[x]-dep[top[x]]+1,x=fa[top[x]]; else return idfn[dfn[x]-k]; } return x; } int dist(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];} int ask_kth(int x,int y,int p){ if(dep[x]-dep[lca(x,y)]>=p)return ask_kth(x,p); else return ask_kth(y,dist(x,y)-p); } void modify(int u,int x){ while(u)T.modify(dfn[top[u]],dfn[u],1,2*n,1,x),u=fa[top[u]]; } ll ask(int u){ ll res=0; while(u)res+=T.ask(dfn[top[u]],dfn[u],1,2*n,1),u=fa[top[u]]; return res; } ll sdep,scnt; void add(int u,int k){ sdep+=dep[u]*k,scnt+=k; modify(u,k); } ll ask_sum(int u){return sdep+scnt*1ll*dep[u]-2*ask(u);} struct info { int u,r; }; bool in(info a,info b){//b is in a? return dist(a.u,b.u)+b.r<=a.r; } info operator+(info a,info b){ if(in(a,b))return a; if(in(b,a))return b; return (info){ask_kth(a.u,b.u,(a.r+b.r+dist(a.u,b.u))/2-a.r),(a.r+b.r+dist(a.u,b.u))/2}; } info t[maxn]; ll res; ll sm[maxn]; struct _ { int id,sgn; _(int _id,int _sgn){id=_id,sgn=_sgn;} }; vector<_>Q[maxn]; inline int len(int l,int r){return r-l+1;} void solve(int l,int r){ if(l==r)return; int mid=l+r>>1; solve(l,mid);solve(mid+1,r); t[mid]=(info){mid,0};down(i,mid-1,l)t[i]=t[i+1]+(info){i,0}; t[mid+1]=(info){mid+1,0};up(i,mid+2,r)t[i]=t[i-1]+(info){i,0}; sm[mid]=0;up(i,mid+1,r)sm[i]=sm[i-1]+t[i].r; up(i,mid+1,r)Q[i].clear(); int p=mid+1; down(i,mid,l){ while(p<=r&&in(t[i],t[p]))p++; Q[p-1].p_b(_(t[i].u,-1)); res-=len(mid+1,p-1)*1ll*t[i].r; res-=sm[p-1]; res+=len(mid+1,p-1)*1ll*t[i].r*2; } p=mid+1; down(i,mid,l){ while(p<=r&&(!in(t[p],t[i])))p++; Q[p-1].p_b(_(t[i].u,1)); res+=len(mid+1,p-1)*1ll*t[i].r; res+=sm[p-1]; if(p<=r)res+=(sm[r]-sm[p-1])*2; } up(i,mid+1,r){ add(t[i].u,1); for(auto it:Q[i])res+=it.sgn*ask_sum(it.id); } up(i,mid+1,r)add(t[i].u,-1); } void slv(){ n=read(); up(i,1,n-1){ int x=read(),y=read(); link(x,n+i),link(y,n+i); } dfs(1,0);dfs2(1,1);T.bd(1,2*n,1); solve(1,n);cout<<res/2; } int main(){ //freopen("b.in","r",stdin),freopen("b.out","w",stdout); slv(); return 0; }