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;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(a) (a).begin(),(a).end()

template<typename T1, typename T2> inline void chkmin(T1 & x, const T2 & y) {if (y < x) x = y;}
template<typename T1, typename T2> inline void chkmax(T1 & x, const T2 & y) {if (x < y) x = y;}

const int N = 2e5 + 10;
int n;
vector<int> g[N];

void read() {
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(i + n);
        g[v].push_back(i + n);
        g[i + n].push_back(u);
        g[i + n].push_back(v);
        // cout << u << " " << i + n << endl;
        // cout << v << " " << i + n << endl;
    }
}

const int LOG = 20;
int jump[N][LOG];
int h[N];

void dfsLCA(int v, int p) {
    jump[v][0] = p;
    for (int i = 1; i < LOG; ++i) {
        jump[v][i] = jump[jump[v][i - 1]][i - 1];
    }
    for (auto i : g[v]) {
        if (i == p) continue;
        h[i] = h[v] + 1;
        dfsLCA(i, v); 
    }
}

int goUp(int v, int h) {
    for (int i = 0; i < LOG; ++i) {
        if ((h >> i) & 1) {
            v = jump[v][i];
        }
    }
    return v;
}

int lca(int v, int u) {
    if (h[v] < h[u]) swap(u, v);
    v = goUp(v, h[v] - h[u]);
    if (v == u) return v;
    for (int i = LOG - 1; i >= 0; --i) {
        if (jump[v][i] != jump[u][i]) {
            v = jump[v][i];
            u = jump[u][i];
        }
    }
    return jump[v][0];
}

int dist(int v, int u) {
    return h[v] + h[u] - 2 * h[lca(v, u)]; 
}

bool used[N];
int sz[N];
int centr;

void dfsCentroid(int v, int p, int size) {
    sz[v] = 1;
    int mx = 0;
    for (auto i : g[v]) {
        if (used[i]) continue;
        if (i == p) continue;
        dfsCentroid(i, v, size);
        sz[v] += sz[i];
        chkmax(mx, sz[i]);
    }
    chkmax(mx, size - sz[v]);
    if (mx * 2 <= size) {
        centr = v;
    }
}

int par[N];
int indSon[N];
ll myDist[N];
vector<ll> sumDist[N];
int myCnt[N];
vector<int> sumCnt[N];

void buildCentroid(int v, int p, int ind, int size) {
    centr = -1;
    dfsCentroid(v, -1, size);
    //cerr << "v = " << v << " p = "<< p << " ind = " << ind << " size = " << size << endl;
    v = centr;
    assert(v != -1);
    // cout << "v = " << v << " p = " << p << " ind = " << ind << " size = " << size << endl; 
    par[v] = p;
    indSon[v] = ind;
    used[v] = true;
    int it = 0;

    for (auto i : g[v]) {
        if (used[i]) continue;
        int fsz = sz[i];
        if (fsz > sz[v]) {
            fsz = size - sz[v];
        }
        buildCentroid(i, v, it++, fsz);    
    }

    sumDist[v].assign(it, 0);
    sumCnt[v].assign(it, 0);
}

void build() {
    dfsLCA(0, 0);
    buildCentroid(0, -1, -1, 2 * n - 1);
}

int goPath(int v, int u, int len) {
    int l = lca(v, u);
    if (h[v] - h[l] < len) {
        v = goUp(u, dist(v, u) - len);
    } else {
        v = goUp(v, len);
    }
    return v;
}

bool checkIn(int v1, int r1, int v2, int r2) {
    return dist(v1, v2) <= r1 - r2;
}

tuple<int, int> merge(int v1, int r1, int v2, int r2) {
    if (dist(v1, v2) <= max(r1, r2) - min(r1, r2)) {
        if (r2 > r1) {
            v1 = v2;
            r1 = r2;
        }
    } else {
        int R = dist(v1, v2) + r1 + r2;
        assert(R % 2 == 0);
        R /= 2;
        int V = goPath(v1, v2, R - r1);
        v1 = V;
        r1 = R;
    }
    return {v1, r1};
}

// deque<int> q;
// set<int> have;

void addV(int v) {
    // have.insert(v);
    // cerr << "addV = " << v << endl;
    // q.push_back(v);
    int u = v;
    int myInd = -1;
    while (u != -1) {
        myDist[u] += dist(u, v);
        myCnt[u]++;
        // cerr << "addV: " << " v = " << v << " u = " << u << " myInd = " << myInd << endl;
        if (myInd != -1) {
            sumDist[u][myInd] += dist(u, v);
            sumCnt[u][myInd]++;
        }
        myInd = indSon[u];
        u = par[u];
    }
}

void delV(int v) {
    // have.erase(v);
    // cerr << "delV = " << v << endl;
    // assert(q.front() == v);
    // q.pop_front();
    int u = v;
    int myInd = -1;
    while (u != -1) {
        myDist[u] -= dist(u, v);
        myCnt[u]--;
        if (myInd != -1) {
            sumDist[u][myInd] -= dist(u, v);
            sumCnt[u][myInd]--;
        }
        myInd = indSon[u];
        u = par[u];
    }
}

ll getAns(int v) {
    ll ans = 0;
    // cerr << "have = " << endl;
    // for (auto i : have) cerr << i << " ";
    // cerr << endl;
    // for (auto i : q) {
    //     ans += dist(v, i);
    // }
    // cerr << "v = " << v << " ans = " << ans << endl;
    int u = v;
    int myInd = -1;
    while (u != -1) {
        // myDist[u] += dist(u, v);
        // myCnt[u]++;
        ans += myDist[u];
        ans += (ll) myCnt[u] * dist(u, v);
        if (myInd != -1) {
            // sumDist[u][myInd] += dist(u, v);
            // sumCnt[u][myInd]++;
            ans -= sumDist[u][myInd];
            ans -= (ll) sumCnt[u][myInd] * dist(u, v);
        }
        myInd = indSon[u];
        u = par[u];
    }
    // cerr << "v = " << v << " ans = " << ans << endl;
    // int fans = 0;
    // for (auto i : have) {
    //     fans += dist(i, v);
    // }
    // assert(ans == fans);
    return ans;
}

ll ans;

int vL[N], rL[N], vR[N], rR[N];
ll suffR[N];

void solve(int l, int r) {
    if (l + 1 >= r) return;
    int m = (l + r) / 2;
    solve(l, m);
    solve(m, r);
    for (int i = 0; i < m - l; ++i) {
        vL[i] = m - 1 - i;
        rL[i] = 0;
        if (i > 0) {
            tie(vL[i], rL[i]) = merge(vL[i], rL[i], vL[i - 1], rL[i - 1]);
        }
    }
    for (int i = 0; i < r - m; ++i) {
        vR[i] = m + i;
        rR[i] = 0;
        if (i > 0){
            tie(vR[i], rR[i]) = merge(vR[i], rR[i], vR[i - 1], rR[i - 1]);
        }
    }
    for (int i = r - m - 1; i >= 0; --i) {
        suffR[i] = rR[i];
        if (i != r - m - 1) {
            suffR[i] += suffR[i + 1];
        }
    }
    /*for (int i = 0; i < m - l; ++i) {
        for (int j = 0; j < r - m; ++j) {
            int V, R;
            tie(V, R) = merge(vL[i], rL[i], vR[j], rR[j]);
            ans += R;
        }
    }*/
    int L = 0;
    int R = 0;
    // q.clear();
    // have.clear();
    for (int i = 0; i < m - l; ++i) {
        while (R < r - m && !checkIn(vR[R], rR[R], vL[i], rL[i])) {
            addV(vR[R]);
            ++R;
        }
        while (L < R && checkIn(vL[i], rL[i], vR[L], rR[L])) {
            delV(vR[L]);
            ++L;
        }
        // for (int j = 0; j < L; ++j) {
        //     ans += rL[i] * 2;
        // }
        ans += (ll)L * rL[i] * 2;

        // for (int j = R; j < r - m; ++j) {
        //     ans += rR[j] * 2;
        // }
        if (R < r - m) {
            ans += suffR[R] * 2;
        }
        // deque<int> have;
        // for (int j = L; j < R; ++j) {
        //     have.push_back(vR[j]);
        // }
        // assert(have == q);
        // for (int j = L; j < R; ++j) {
        //     // ans += rL[i] + rR[j] + dist(vL[i], vR[j]);
        //     // ans += rL[i] + rR[j];
        //     ans += rR[j];
        // }
        if (R - L > 0) {
            ans += suffR[L];
            if (R < r - m) {
                ans -= suffR[R];
            }
        }
        ans += (ll) rL[i] * (R - L);
        ans += getAns(vL[i]);
    }
    while (L < R) {
        delV(vR[L]);
        ++L;
    }
}

void solve() {
    ans = 0;
    solve(0, n);
}

void run() {
    build();
    //cerr << "buildOk" << endl;
    solve();
}

void write() {
    assert(ans % 2 == 0);
    cout << ans / 2 << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(20), cout.setf(ios::fixed);
    read();
    run();
    write();
    return 0;
}