Problem: You are given a tree with n vertices numbered 1, …, n. A tree is a connected simple graph without cycles.

Let dist(u, v) be the number of edges in the unique simple path connecting vertices u and v.

Let diam(l, r) = max dist(u, v) over all pairs u, v such that l ≤ u, v ≤ r.

Compute ∑_{1 ≤ l ≤ r ≤ n} diam(l, r).

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of vertices in the tree.

The next n - 1 lines describe the tree edges. Each of these lines contains two integers u, v (1 ≤ u, v ≤ n) — endpoint indices of the respective tree edge. It is guaranteed that the edge list indeed describes a tree.

Output

Print a single integer — ∑_{1 ≤ l ≤ r ≤ n} diam(l, r).

Examples

Input


4
1 2
2 4
3 2


Output


10


Input


10
1 8
2 9
5 6
4 8
4 2
7 9
3 6
10 4
3 9


Output


224

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
struct edge{int to,next;}e[N<<1];int h[N],ecnt=1;
inline void addedge(int x,int y){
	e[++ecnt]=(edge){y,h[x]};h[x]=ecnt;
	e[++ecnt]=(edge){x,h[y]};h[y]=ecnt;
}
namespace N1{
bool vi[N];
int f[N],sz[N],sum,rt;
void getrt(int x,int fa){	
	f[x]=0;sz[x]=1;
	for(int i=h[x];i;i=e[i].next)if(e[i].to!=fa && !vi[e[i].to]){
		getrt(e[i].to,x);sz[x]+=sz[e[i].to];
		f[x]=max(f[x],sz[e[i].to]);
	}
	f[x]=max(f[x],sum-sz[x]);if(f[x]<f[rt])rt=x;
}
struct atom{int rt,bel,d;};
vector<atom>anc[N];
ll s1[N],s2[N],s3[N],s4[N];
int md;
void getdep(int x,int fa,int y,int d){
	if(d>md)md=d;anc[x].push_back((atom){rt,y,d});
	for(int i=h[x];i;i=e[i].next)if(e[i].to!=fa && !vi[e[i].to])getdep(e[i].to,x,y,d+1);
}
void solve(int x){
	vi[x]=1;
	int mdd=0;
	for(int i=h[x];i;i=e[i].next)if(!vi[e[i].to]){
		if(sz[e[i].to]>sz[x])sz[e[i].to]=sum-sz[x];
		md=0;getdep(e[i].to,x,i>>1,1);
		mdd=max(mdd,md);
	}
	anc[x].push_back((atom){x,0,0});
	for(int i=h[x];i;i=e[i].next)if(!vi[e[i].to])sum=sz[e[i].to],rt=0,getrt(e[i].to,x),solve(rt);
}
inline void mdy(int x,int k){
	for(auto u:anc[x]){
		s1[u.rt]+=k*u.d;
		s2[u.bel]+=k*u.d;
		s3[u.rt]+=k;
		s4[u.bel]+=k;
	}
}
inline ll query(int x,int d){
	ll ret=0;
	for(auto u:anc[x])if(d>=u.d){
		ret+=s1[u.rt];
		ret-=s2[u.bel];
		ret+=1ll*s3[u.rt]*u.d;
		ret-=1ll*s4[u.bel]*u.d;
	}
	return ret;
}
inline void ini(int n){
	sum=n;f[0]=1<<30;memset(vi+1,0,n);
	getrt(1,0);solve(rt);
}
}
int n,i,j,x,y;
namespace N2{
int dad[N],dep[N],sz[N],ma[N],top[N],be[N],en[N],dfn[N],dcnt;
ll bi1[N],bi2[N];
inline void add(ll*bi,int x,int v){for(;x<=n;x+=x&-x)bi[x]+=v;}
inline ll ask(ll*bi,int x){int ans=0;for(;x;x-=x&-x)ans+=bi[x];return ans;}
inline void mdy(int x,int k){
	add(bi1,be[x],dep[x]*k);add(bi2,be[x],k);
}
inline pair<ll,int>ask(int x){
	ll v1=(ask(bi1,en[x])-ask(bi1,be[x]-1));int v2=(ask(bi2,en[x])-ask(bi2,be[x]-1));
	return make_pair(v1-1ll*v2*dep[x],v2);
}
void dfs1(int x,int fa){
	sz[x]=1;
	for(int i=h[x],y;i;i=e[i].next)if(y=e[i].to,y!=fa){
		dad[y]=x;dep[y]=dep[x]+1;dfs1(y,x);
		sz[x]+=sz[y];if(sz[y]>sz[ma[x]])ma[x]=y;
	}
}
void dfs2(int x,int fa){
	dfn[be[x]=++dcnt]=x;
	if(ma[x])top[ma[x]]=top[x],dfs2(ma[x],x);
	for(int i=h[x],y;i;i=e[i].next)if(y=e[i].to,y!=fa){if(y!=fa && y!=ma[x])top[y]=y,dfs2(y,x);}
	en[x]=dcnt;
}
inline int lca(int x,int y){
	for(;top[x]!=top[y];y=dad[top[y]])if(dep[top[x]]>dep[top[y]])swap(x,y);
	return dep[x]<dep[y]?x:y;
}
inline int ka(int x,int k){
	for(;dep[x]-dep[top[x]]<k;k-=dep[x]-dep[top[x]]+1,x=dad[top[x]]);
	return dfn[be[x]-k];
}
inline int dis(int x,int y){return dep[x]+dep[y]-dep[lca(x,y)]*2;}
inline void ini(){
	dfs1(1,0);top[1]=1;dfs2(1,0);
}
}
using N2::dis;
using N2::dep;
using N2::dad;
struct atom{
	int x,y,d;
	inline bool testt(int u){
		return !x || !y || max(dis(x,u),dis(y,u))>d;
	}
};
inline atom uni(const atom&a,const atom&b){
	if(!a.x)return b;if(!b.x)return a;int x,y,md=-1,d;
	auto upd=[&](int xx,int yy,int d=-1){if(d==-1)d=dis(xx,yy);if(d>md)md=d,x=xx,y=yy;};
	upd(a.x,a.y,a.d);upd(b.x,b.y,b.d);
	upd(a.x,b.x);upd(a.x,b.y);upd(a.y,b.x);upd(a.y,b.y);
	return atom{x,y,md};
}
ll ASS;
int TOT;
inline ll calc(int x,int y){
	int d=dis(x,y),z;
	if(dep[x]>dep[y])swap(x,y);z=N2::ka(y,d/2);
	ll s1,s2;int c1,c2;tie(s2,c2)=N2::ask(z);
	if(d&1){
		s1=N1::query(dad[z],N);c1=TOT;
		s1-=s2+c2;c1-=c2;
	}else{
		s1=N1::query(z,N);c1=TOT;
		s1-=s2;c1-=c2;
	}
	return s1+s2+1ll*(d+1>>1)*(c1+c2);
}
atom a[N];
vector<pair<int,int>>ve[N];
void solve(int l,int r){
	if(l==r)return;
	int m=l+r>>1;solve(l,m);solve(m+1,r);
	static ll su[N];int i,j,k;
	a[m+1]=atom{m+1,m+1,0};for(i=m+2;i<=r;++i)a[i]=uni(a[i-1],atom{i,i,0});
	a[m]=atom{m,m,0};for(i=m-1;i>=l;--i)a[i]=uni(a[i+1],atom{i,i,0});
	for(i=l;i<=m+1;++i)ve[i].clear();
	su[l-1]=0;for(i=l;i<=m;++i)su[i]=su[i-1]+a[i].d;
	for(j=k=m+1,i=m+1;i<=r;++i){
		for(;j>l && (a[j-1].testt(a[i].x) || a[j-1].testt(a[i].y));--j);
		for(;k>j && !(a[i].testt(a[k-1].x) || a[i].testt(a[k-1].y));--k);
		ASS+=1ll*(m+1-k)*a[i].d+su[j-1];
		if(j<k){
			int d1,d2,x;
			d1=max(dis(a[j].x,a[i].x),dis(a[j].y,a[i].x));d2=max(dis(a[j].x,a[i].y),dis(a[j].y,a[i].y));
			x=d1>d2?a[i].x:a[i].y;
			ve[j].push_back({x,1});ve[k].push_back({x,-1});
		}
	}
	for(i=l;i<=m+1;++i){
		for(auto u:ve[i]){
			int x,y;tie(x,y)=u;
			N1::mdy(x,y);N2::mdy(x,y);TOT+=y;
		}
		if(i<=m)ASS+=calc(a[i].x,a[i].y);
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(i=1;i<n;++i){
		cin>>x>>y;
		addedge(x,y);
	}
	N1::ini(n);N2::ini();
	solve(1,n);
	cout<<ASS<<endl;
}