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;
#define maxn 200100
#define ll long long
vector<int>v[maxn];
int n,fa[maxn],top[maxn],de[maxn],hv[maxn],si[maxn],f[maxn][20],lg[maxn];
void dfs1(int x,int f){
	fa[x]=f,de[x]=de[f]+1;
	si[x]=1;
	for(int y:v[x]){
		if(y!=f){
			dfs1(y,x);
			si[x]+=si[y];
			if(si[y]>si[hv[x]])hv[x]=y;
		}
	}
}
void dfs2(int x,int t){
	top[x]=t;
	f[x][0]=fa[x];
	for(int i=1;i<=19;i++)f[x][i]=f[f[x][i-1]][i-1];
	if(hv[x])dfs2(hv[x],t);
	for(int y:v[x]){
		if(y!=fa[x]&&y!=hv[x])
		dfs2(y,y);
	} 
}
int getlca(int x,int y){
	while(top[x]!=top[y]){
		if(de[top[x]]<de[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	return de[x]<de[y]?x:y;
}
int jump(int x,int y){
    for(int i=0;y;i++)
    if(y>>i&1)x=f[x][i],y-=1<<i;
    return x;
} 
struct cir{
	int x,r;
	cir(int a=0,int b=0){x=a,r=b;} 
};
bool in(cir a,cir b){//whether a is in b
    int d=de[a.x]+de[b.x]-2*de[getlca(a.x,b.x)];
	if(a.r+d<=b.r)return 1;
	return 0; 
}
cir merge(cir a,cir b){
	int lca=getlca(a.x,b.x);
	int d=de[a.x]+de[b.x]-2*de[lca];
	if(a.r+d<=b.r)return b;
	if(b.r+d<=a.r)return a;
	int da=(d-a.r+b.r)/2;
	int db=(d+a.r-b.r)/2;
	int nx;
	if(da<=de[a.x]-de[lca])nx=jump(a.x,da);
	else nx=jump(b.x,db);
	return cir(nx,(d+a.r+b.r)/2);
}
struct tr{
	int vis[maxn],rt,rtm,si[maxn];
    void find(int x,int fa,int n){
    	si[x]=1;
    	int cur=0;
    	for(int y:v[x]){
    		if(y==fa||vis[y])continue;
    		find(y,x,n); 
    		si[x]+=si[y];
    		cur=max(cur,si[y]);
		}
		cur=max(cur,n-si[x]);
		if(cur<rtm)rtm=cur,rt=x;
	}
	void calcsi(int x,int fa){
		si[x]=1;
		for(int y:v[x])
		if(fa!=y&&!vis[y])calcsi(y,x),si[x]+=si[y]; 
	}
	int fa[maxn];
	void build(int x,int f,int n){
		rtm=1e9;
		find(x,0,n);
		x=rt;fa[x]=f;
		vis[x]=1;
		calcsi(x,0);
		assert(si[x]==n); 
		for(int y:v[x]){
			if(vis[y])continue;
			build(y,x,si[y]);
		}
	}
	int d[maxn][30];
	void init(){
		for(int i=1;i<=n*2-1;i++){
			for(int j=0,x=i;x;x=fa[x],j++){
				d[i][j]=de[i]+de[x]-2*de[getlca(i,x)];
			}
		}
	}
	void lets_go(){
		build(1,0,n*2-1);
		init();
	}
	int c[maxn];
	ll v1[maxn],v2[maxn];
	void add(int x,int v){
		for(int i=0,j=x;j;i++,j=fa[j]){
			c[j]+=v;v1[j]+=1ll*v*d[x][i];
			if(fa[x])
			v2[j]+=1ll*v*d[x][i+1];
		}
	}
	ll sum(int x){
		ll ans=0;
		for(int i=0,j=x;j;i++,j=fa[j]){
			ans+=v1[j]+1ll*d[x][i]*c[j];
			if(fa[x])
			ans-=v2[j]+1ll*d[x][i+1]*c[j];
		}
		return ans;
	}
}dt;
ll sr[maxn];
cir sc[maxn];
ll go(int l,int r){
	if(l==r)return 0;
	int mid=l+r>>1;
	ll ans=go(l,mid)+go(mid+1,r);
	sr[mid]=sr[mid+1]=0;
	sc[mid+1]=cir(mid+1,0);
	for(int i=mid+2;i<=r;i++){
		sc[i]=merge(sc[i-1],cir(i,0));
		sr[i]=sr[i-1]+sc[i].r;
	} 
	int p1=mid+1,p2=mid;
	cir cur;
	for(int i=mid;i>=l;i--){
	    if(i==mid)cur=cir(mid,0);
	    else cur=merge(cur,cir(i,0));
		while(p2<r&&!in(cur,sc[p2+1]))p2++,dt.add(sc[p2].x,1);
		while(p1<=p2&&in(sc[p1],cur))dt.add(sc[p1].x,-1),p1++;
		ans+=1ll*cur.r*(p1-mid-1)+sr[r]-sr[p2];
		ans+=(dt.sum(cur.x)+1ll*cur.r*(p2-p1+1)+sr[p2]-sr[p1-1])/2;		
	}
    while(p1<=p2)dt.add(sc[p1].x,-1),p1++;
    return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y; 
		v[x].push_back(n+i);
		v[y].push_back(n+i);
		v[n+i].push_back(x);
		v[n+i].push_back(y);
	}
	dfs1(1,0);
	dfs2(1,1);
	dt.lets_go();
	cout<<go(1,n);
	return 0;
}