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:
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mkp make_pair 
#define si set < int >
#define vi vector < int > 
#define pii pair < int, int > 
#define mii map < int, int >
#define p_q priority_queue
#define INF ((1 << 30) - 1)
#define FI(n) FastIO::read(n)
#define FO(n) FastIO::write(n)
#define ull unsigned long long
#define mst(a, b) memset(a,b,sizeof(a))
#define foR(i, k, j) for(int i = (k); i >= (j); i--)
#define For(i, k, j) for(int i = (k); i <= (j); i++)
#define Foe(i, u) for(int i = lst[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define Fin(s) freopen(s, "r", stdin)
#define Fout(s) freopen(s, "w", stdout)
#define file(s) Fin(s".in"), Fout(s".out")
#define int long long
const int P = 1e9 + 7; //
using namespace std;
template <typename T> inline void ckmax(T &a, T b) {(a < b) && (a = b);}
template <typename T> inline void ckmin(T &a, T b) {(a > b) && (a = b);}
inline int mul(int a, int b) {return 1ll * a * b % P;}
inline int add(int a, int b) {return a + b >= P ? a + b - P : a + b;}
inline int sub(int a, int b) {return a - b >= 0 ? a - b : a - b + P;}
inline void mulmod(int &a, int b) {a = mul(a, b);}
inline void addmod(int &a, int b) {((a += b) >= P) && (a -= P);}
inline void submod(int &a, int b) {((a -= b) < 0) && (a += P);}
inline int ksm(int a, int b) {int ans=1; for(;b;b>>=1) {if(b&1) ans=1ll*ans*a%P;a=1ll*a*a%P;}return ans;}
inline int inv(int a) {return ksm(a, P-2);}
namespace FastIO {
    const int SIZE=1<<16; char buf[SIZE], obuf[SIZE], str[64]; int bi=SIZE, bn=SIZE, opt;
    int read(char *s) {
        while (bn) {for (;bi<bn&&buf[bi]<=' ';bi++);if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}
        int sn=0;while (bn) {for (;bi<bn&&buf[bi]>' ';bi++) s[sn++]=buf[bi];if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}s[sn]=0;return sn;
    }
    bool read(int& x) {if(x)x=0;int bf=0,n=read(str); if(!n) return 0; int i=0; if (str[i]=='-') bf=1,i=1; for(x=0;i<n;i++) x=x*10+str[i]-'0'; if(bf) x=-x; return 1;}
    void write(int x) {
        if(!x) obuf[opt++] = '0'; else {if(x<0) obuf[opt++]='-',x=-x;int sn=0; while(x)str[sn++]=x%10+'0',x/=10;for (int i=sn-1;i>=0;i--) obuf[opt++]=str[i];}
        if (opt>=(SIZE>>1)){fwrite(obuf, 1, opt, stdout); opt=0;}
    }
    void write(char x) {obuf[opt++]=x;if (opt>=(SIZE>>1)){fwrite(obuf, 1, opt, stdout); opt=0;}}
    void Fflush() { if (opt) fwrite(obuf, 1, opt, stdout); opt=0;}
};
inline int read() {int x; FI(x); return x;}
const int MAXN = 2e5 + 5;
ll ans = 0;
vector < int > e[MAXN];
int a[MAXN], n, m;

namespace BAS {
	const int N = 200005;
	const int LOGN = 19;
	int dep[N], dfn[N], pa[LOGN][N], lg2[N * 2], st[LOGN][N * 2], dfc;
	void pre_dfs(int u, int lst, int depth) {
		dep[u] = depth;
		pa[0][u] = lst;
		st[0][dfn[u] = ++dfc] = u;
		for (int v : e[u]) if (v != lst) {
			pre_dfs(v, u, depth + 1);
			st[0][++dfc] = u;
		}
	}	
	inline void Pre() {
		lg2[0] = -1;
		for (int i = 1; i <= dfc; i++) lg2[i] = lg2[i - 1] + ((i & (i - 1)) ? 0 : 1);
		for (int i = 1; i <= lg2[dfc]; i++) {
			for (int j = 1; j + (1 << i) - 1 <= dfc; j++) {
				if (dep[st[i - 1][j]] < dep[st[i - 1][j + (1 << (i - 1))]])
					st[i][j] = st[i - 1][j];
				else
					st[i][j] = st[i - 1][j + (1 << (i - 1))];
			}
		}
		for (int i = 1; i < LOGN; i++)
			for (int u = 1; u <= 2 * n - 1; u++)
				pa[i][u] = pa[i - 1][pa[i - 1][u]];
	}
	inline int LCA(int l, int r) {
		l = dfn[l], r = dfn[r];
		if (l > r) swap(l, r);
		int i = lg2[r - l + 1];
		if (dep[st[i][l]] < dep[st[i][r - (1 << i) + 1]])
			return st[i][l];
		else
			return st[i][r - (1 << i) + 1];
	}
	inline int Dist(int u, int v) {
		return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
	}
	inline int Anc(int u, int k) {
		for (int i = 0; i < LOGN; i++) if (k >> i & 1) u = pa[i][u];
		return u;
	}
	inline int go(int u, int v, int k) {
		int l = LCA(u, v);
		if(dep[u] - dep[l] < k) {
//			cerr << "?";
			return Anc(v, dep[u] + dep[v] - 2 * dep[l] - k);
		} else return Anc(u, k);
	}
	void init() {pre_dfs(1, 0, 0), Pre();}
}
#define dist(i, j) BAS::Dist(i, j)
#define lca(i, j) BAS::LCA(i, j)
#define kth(u, k) BAS::Anc(u, k)
#define go(u, v, k) BAS::go(u, v, k)
struct Cir {
	int v, r;
	Cir() {v = r = 0;} Cir(int u) : v(u), r(0) {}
	Cir(int V, int R) : v(V), r(R) {}
//	void print() {cerr << v << ' ' << r << endl;}
};
pair < Cir, int > merge(const Cir &a, const Cir &b) {
	int d = dist(a.v, b.v);
//	cerr << a.v << ' ' << a.r << ' ' << b.v << ' ' << b.r << endl;
	if(d + b.r <= a.r) return mkp(a, 0);
	if(d + a.r <= b.r) return mkp(b, 2);
	return mkp(Cir(go(a.v, b.v, (d - a.r + b.r) / 2), (d + a.r + b.r) / 2), 1);
}
int tot_cnt;
namespace DFS {
	int f[MAXN], siz[MAXN], rt, vrt, vis[MAXN], allrt;
//	vector < int > g[MAXN], h[MAXN];
	ll g[MAXN], h[MAXN]; int cg[MAXN], ch[MAXN];
	void getroot(int u, int fa, int allsiz) {
		siz[u] = 1; int mx = 0;
		for(auto v : e[u]) {
			if(vis[v] || v == fa) continue;
			getroot(v, u, allsiz);
			siz[u] += siz[v]; ckmax(mx, siz[v]);
		}
		ckmax(mx, allsiz - siz[u]);
		if(rt == -1 || vrt > mx)
			vrt = mx, rt = u;	
	}
	void getinfo(int u, int fa) {
		siz[u] = 1; 
		for(auto v : e[u]) {
			if(vis[v] || v == fa) continue;
			getinfo(v, u);
			siz[u] += siz[v]; 
		}	
	}
	void dfs(int u, int allsiz) {
		vis[u] = 1; getinfo(u, 0); allsiz = siz[u];
		for(auto v : e[u]) {
			if(vis[v]) continue;
			int t = siz[v]; vrt = INF; 
			getroot(v, u, t); f[rt] = u; dfs(rt, t);
		}
	}
	inline void init() {
		vrt = INF; getroot(1, 0, n); allrt = rt;dfs(rt, n);	
//		For(u, 1, n) cerr << dep[u] << endl, assert(dep[u] <= 1000);
	}
	
	inline void update(int u, int op) {
//		fprintf(stderr, "Update %d %d\n", u, op);
		int s = u, fr = -1;
		while(u) {
			int d = dist(s, u); g[u] += op * d, cg[u] += op;
			if(fr != -1) h[fr] += op * d, ch[fr] += op;
			fr = u, u = f[u];
		}
	}
	inline ll query(int u) {
		int s = u, fr = -1;
		ll ans = 0; 
		while(u) {
//			tot_cnt++;if(tot_cnt % 100000 == 0) cerr << tot_cnt << endl;
			int d = dist(s, u); ans += (g[u] - h[fr]) + 1ll * (cg[u] - cg[fr]) * d;
			fr = u, u = f[u];
		}
//		assert(ans % 2 == 0);
		return ans;
	}
}
Cir val[MAXN]; int suf[MAXN]; int L, R;
void cdq(int l, int r) {
//	fprintf(stderr, "cdq : %d %d\n", l, r); 
	if(l == r) return; ll sum = 0;
	int mid = (l + r) >> 1; L = mid + 1, R = mid;
	val[mid + 1] = Cir(mid + 1); For(i, mid + 2, r) val[i] = merge(val[i - 1], Cir(i)).first;
	suf[r + 1] = 0; foR(i, r, mid - 1) suf[i] = suf[i + 1] + val[i].r;
	val[mid] = Cir(mid); int pos1 = mid, pos2 = mid; foR(i, mid, l) {
		if(i != mid) val[i] = merge(val[i + 1], Cir(i)).first;
		while(pos1 < r && merge(val[i], val[pos1+1]).second == 0) pos1++;
		while(pos2 <= r && merge(val[i], val[pos2]).second != 2) pos2++;
		while(L <= pos1) sum -= val[L].r, DFS::update(val[L++].v, -1);
		while(R < pos2 - 1) DFS::update(val[++R].v, 1), sum += val[R].r;
//		cerr << i << ' ' << pos1 << ' ' << pos2 << endl;
		ans += 2ll * (pos1 - mid) * val[i].r
			+ 2ll * suf[pos2]
			+ DFS::query(val[i].v) + 1ll * (pos2 - pos1 - 1) * val[i].r + sum;
//		fprintf(stderr, "add %lld %lld %lld\n", 2ll * (pos1 - mid) * merge(val[i], val[pos1]).first.r , DFS::query(val[i].v) + 1ll * (pos2 - pos1 - 1) * val[i].r + sum, 2ll * suf[pos2]);
//		cerr << "Query " << i << ' ' << DFS::query(i) << endl;
	}
//	For(i, l, r) val[i].print();
	For(i, L, R) DFS::update(val[i].v, -1);
	cdq(l, mid), cdq(mid+1, r);
}
signed main()
{
    #ifndef ONLINE_JUDGE
		file("pro");
    #endif
	n = m = read();
	For(i, 1, n - 1) {
		int u = read(), v = read();
		e[u].pb(++m), e[v].pb(m); e[m].pb(u), e[m].pb(v);
    }
   
    BAS::init(); DFS::init(); 
//	cerr << lca(4, 1) << ' ' << go(4, 1, 1) << endl;
    cdq(1, n);
//    cerr << ans << endl;
	assert(ans % 2 == 0);
//	cerr << tot_cnt << endl;
	cout << ans / 2 << endl;
	return FastIO::Fflush(), 0;
}