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>
typedef int LL;
typedef long long ll;
#define pii std::pair<LL,LL>
#define pb push_back
const LL maxn=2e5+9,inf=0x3f3f3f3f;
LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1; c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
	}return x*f;
}
void Chkmax(LL &x,LL y){
	if(y>x) x=y;
}
void Chkmin(LL &x,LL y){
	if(y<x) x=y;
}
LL nod;
namespace Tree{
	LL tim;
	LL dfn[maxn],dep[maxn];
	LL up[maxn][18],inc[maxn<<1][19],pos[maxn<<1],lg[maxn<<1];
	std::vector<LL> V[maxn];
	void Add(LL u,LL v){
		V[u].pb(v); V[v].pb(u);
	}
	void Dfs(LL u,LL f){
		dep[u]=dep[f]+1;
		up[u][0]=f;
		for(LL i=1;i<=17;++i) up[u][i]=up[up[u][i-1]][i-1];
		dfn[u]=++tim; pos[tim]=u;
		//printf("%d\n",tim);
		for(LL i=0;i<V[u].size();++i){
			LL v(V[u][i]); if(v==f) continue;
			Dfs(v,u);
			pos[++tim]=u;
		}
	}
	LL Lca(LL x,LL y){
		if(x==y) return x;
		x=dfn[x]; y=dfn[y];
		if(x>y) std::swap(x,y);
		LL len(lg[y-x+1]-1);
		x=inc[x][len]; y=inc[y-(1<<len)+1][len];
		return dep[x]<dep[y]?x:y;
	}
	LL Dis(LL x,LL y){
		return dep[x]+dep[y]-(dep[Lca(x,y)]<<1);
	}
	LL Walk(LL x,LL y,LL len){
		LL lca(Lca(x,y));
		if(dep[x]-dep[lca]>=len){
			for(LL i=0;i<=17;++i) if((len>>i)&1){
				x=up[x][i];
			}
			return x;
		}else{
			len-=dep[x]-dep[lca];
			len=dep[y]-dep[lca]-len;
			for(LL i=0;i<=17;++i) if((len>>i)&1){
				y=up[y][i];
			}
			return y;
		}
	}
	void Init(){
		Dfs(1,0);
		//printf("%d\n",tim);
		for(LL i=1;i<=tim;++i) lg[i]=lg[i>>1]+1;
		for(LL i=1;i<=tim;++i) inc[i][0]=pos[i];
		for(LL i=1;i<=18;++i){
			for(LL j=1;j+(1<<i-1)<=tim;++j){
				LL x(inc[j][i-1]),y(inc[j+(1<<i-1)][i-1]);
				inc[j][i]=(dep[x]<dep[y]?x:y);
			}
		}
	}
}
namespace Dct{
	LL root,N;
	LL mx[maxn],vis[maxn];
	LL size[maxn],fa[maxn],sizex[maxn],sizef[maxn];
	ll sumx[maxn],sumf[maxn];
	std::vector<LL> V[maxn];
	void Add(LL x,LL y){
		V[x].pb(y); V[y].pb(x);
	}
	void Find(LL u,LL f){
		size[u]=1;
		mx[u]=0;
		for(LL i=0;i<V[u].size();++i){
			LL v(V[u][i]); if(v==f || vis[v]) continue;
			Find(v,u); size[u]+=size[v];
			Chkmax(mx[u],size[v]);
		}
		Chkmax(mx[u],N-size[u]);
		if(mx[u]<mx[root]){
			root=u;
		}
	}
	LL Solve(LL u,LL d){
		LL tmp(u);
		root=0; Find(u,0);
		u=root; Find(u,0);
		vis[u]=1;
		//printf("(%d,%d)\n",tmp,u);
		//exit(0);
		/*
		if(d%10==0){
			printf("# %d\n",d);
		}
		*/
		for(LL i=0;i<V[u].size();++i){
			LL v(V[u][i]); if(vis[v]) continue;
			N=size[v];
			LL x(Solve(v,d+1));
			fa[x]=u;
		}
		return u;
	}
	void Insert(LL x){
		for(LL u=x;u;u=fa[u]){
			LL f(fa[u]);
			if(f){
				sumf[u]+=Tree::Dis(x,f); sizef[u]++;
			}
			sumx[u]+=Tree::Dis(x,u); sizex[u]++;
		}
	}
	void Erase(LL x){
		for(LL u=x;u;u=fa[u]){
			LL f(fa[u]);
			if(f){
				sumf[u]-=Tree::Dis(x,f); sizef[u]--;
			}
			sumx[u]-=Tree::Dis(x,u); sizex[u]--;
		}
	}
	ll Query(LL x){
		ll ret(0);
		for(LL u=x;u;u=fa[u]){
			ret+=1ll*sizex[u]*Tree::Dis(x,u);
			ret+=1ll*sumx[u];
			LL f(fa[u]);
			if(f){
				ret-=1ll*sizef[u]*Tree::Dis(x,f);
				ret-=1ll*sumf[u];
			}
		}
		return ret;
	}
	void Init(){
		N=nod; mx[0]=inf;
		Solve(1,0);
	}
}
ll ans;
ll suf[maxn],pre[maxn];
pii c1[maxn],c2[maxn],t1[maxn],t2[maxn];
bool Check(pii A,pii B){
	LL len(Tree::Dis(A.first,B.first));
	return len<=A.second-B.second;
}
void Solve(LL L,LL R){
	if(L==R) return;
	//printf("(%d,%d)\n",L,R);
	LL mid(L+R>>1);
	c1[mid]=pii(mid,0);
	for(LL i=mid-1;i>=L;--i){
		if(Tree::Dis(i,c1[i+1].first)<=c1[i+1].second){
			c1[i]=c1[i+1];
		}else{
			c1[i].second=c1[i+1].second+Tree::Dis(i,c1[i+1].first)>>1;
			LL tmp(c1[i].second-c1[i+1].second);
			c1[i].first=Tree::Walk(c1[i+1].first,i,tmp);
		}
	}
	c2[mid+1]=pii(mid+1,0);
	for(LL i=mid+2;i<=R;++i){
		if(Tree::Dis(i,c2[i-1].first)<=c2[i-1].second){
			c2[i]=c2[i-1];
		}else{
			c2[i].second=c2[i-1].second+Tree::Dis(i,c2[i-1].first)>>1;
			LL tmp(c2[i].second-c2[i-1].second);
			c2[i].first=Tree::Walk(c2[i-1].first,i,tmp);
		}
	}
	pre[L-1]=0;
	for(LL i=L;i<=mid;++i){
		pre[i]=pre[i-1]+c1[i].second;
	}
	suf[R+1]=0;
	for(LL i=R;i>mid;--i){
		suf[i]=suf[i+1]+c2[i].second;
	}
	t1[mid+1]=pii(mid,mid);
	for(LL i=mid;i>=L;--i){
		LL l(t1[i+1].first),r(t1[i+1].second);
		while(l+1<=R && Check(c1[i],c2[l+1])){
			++l;
		}
		Chkmax(r,l+1);
		while(r<=R && !Check(c2[r],c1[i])){
			++r;
		}
		t1[i]=pii(l,r);
	}
//	/*
	for(LL i=mid;i>=L;--i){
		if(i==mid){
			LL l(t1[i].first),r(t1[i].second);
			for(LL j=l+1;j<r;++j){
				//printf("Insert %d\n",j);
				LL x(c2[j].first);
			    Dct::Insert(x);
			}
		}else{
			LL l1(t1[i+1].first),r1(t1[i+1].second);
			LL l2(t1[i].first),r2(t1[i].second);
			for(LL j=r1;j<r2;++j){
				//printf("Insert %d\n",j);
				LL x(c2[j].first);
				Dct::Insert(x);
			}
			for(LL j=l1+1;j<=l2;++j){
				//printf("Erase %d\n",j);
				LL x(c2[j].first);
				Dct::Erase(x);
			}
		}
		LL l(t1[i].first),r(t1[i].second);
		if(l>=mid+1) ans+=2ll*c1[i].second*(l-mid);
		if(r<=R) ans+=2ll*suf[r];
	//	
	    //printf("%d,%d\n",l,r);
		if(l+1<r){
			ll tmp(ans); LL x(c1[i].first);
			ans+=1ll*c1[i].second*(r-l-1);
			ans+=(suf[l+1]-suf[r]);
			//printf("%lld\n",ans-tmp);
			ans+=Dct::Query(x);
			//printf("%lld\n",Dct::Query(x));
		}
	//	
	}
	
	//printf("# %lld\n",ans);
	for(LL i=t1[L].first+1;i<t1[L].second;++i){
		LL x(c2[i].first);
		//printf("Erase %d\n",x);
		Dct::Erase(x);
	}
	Solve(L,mid); Solve(mid+1,R);
}
int main(){
	LL n=Read();
	nod=n;
	for(LL i=1;i<n;++i){
		LL x(Read()),y(Read());
		++nod;
		{
			Dct::Add(x,nod); Tree::Add(x,nod);
		}
		{
			Dct::Add(y,nod); Tree::Add(y,nod);
		}
	}
	//printf("# %d\n",nod);
	//puts("033");
	Tree::Init();
	//puts("033");
	Dct::Init();
	//puts("033");
	//exit(0);
	Solve(1,n);
	assert(ans%2==0);
	ans/=2;
	printf("%lld\n",ans);
	return 0;
}