Problem 8

#include <bits/stdc++.h>
using namespace std;
// nichijou
#define REP(i,a,b) for (int i(a); i < (b); ++i)
#define RP(i,n) REP(i,0,n)
#define PER(i,a,b) for(int i((a)-1); i >= (b); --i)
#define PR(i,n) PER(i,n,0)
#define REP1(i,a,b) REP(i,a,(b)+1)
#define RP1(i,n) REP1(i,1,n)
#define PER1(i,a,b) PER(i,(a)+1,b)
#define PR1(i,n) PER1(i,n,1)
#define DO(n) RP(__i,n)
template<class T,class U>
bool cmax(T & a, const U & b) {return a < b ? a = b, 1 : 0;}
template<class T,class U>
bool cmin(T & a, const U & b) {return b < a ? a = b, 1 : 0;}

// data type
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second

// STL container
typedef vector<int> vi;
typedef vector<ll> vll;
#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define CLR(a) (a).clear()
#define BK(a) ((a).back())
#define FT(a) ((a).front())
#define DB(a) (a).pop_back()
#define DF(a) (a).pop_front()
#define PB push_back
#define EB emplace_back

/* I gave you my heart and then you turned around. */
void _BG(const char * s) {cerr<<s<<endl;}
template<class T, class ... TT>
void _BG(const char * s,T a, TT...b)
{
    for (size_t c = 0; *s && (c || *s != ','); cerr << *s++)
        c += count(ALL("([{"),*s) - count(ALL(")]}"),*s);
    cerr << " = " << a;
    if (*s) {
        cerr << ", ";
        ++s;
    }
    _BG(s,b...);
}
#ifdef PR3PONY
#define BG(...) do { \
    cerr << __PRETTY_FUNCTION__ << ':' << __LINE__ << ": "; \
    _BG(#__VA_ARGS__,__VA_ARGS__); \
} while(0)
#else
#define BG(...)
#endif

/* Reading input is now 20% cooler! */
bool RD() {return 1;}
bool RD(char & a) {return scanf(" %c", &a) == 1;}
bool RD(char * a) {return scanf("%s", a) == 1;}
bool RD(double & a) {return scanf("%lf", &a) == 1;}
bool RD(int & a) {return scanf("%d", &a) == 1;}
bool RD(ll & a) {return scanf("%lld", &a) == 1;}

template<class T, class ... TT>
bool RD(T & a, TT & ... b) {return RD(a) && RD(b...);}

/* Do princesses dream of magic sheep? */
#define DR(T,...) T __VA_ARGS__; RD(__VA_ARGS__)
#define RI(...) DR(int,__VA_ARGS__)

/* For it's time for you to fulfill your output. */
void PT(const char & a) {putchar(a);}
void PT(char const * const & a) {fputs(a, stdout);}
void PT(const double & a) {printf("%.16f", a);}
void PT(const int & a) {printf("%d", a);}
void PT(const ll & a) {printf("%lld", a);}

/* The line will last forever! */
template<char s = ' ', char e = '\n'>
void PL() {if (e) PT(e);}
template<char s = ' ', char e = '\n', class T, class ... TT>
void PL(const T & a, const TT & ... b)
{PT(a); if (sizeof...(b) && s) PT(s); PL<s,e>(b...);}

/* Good Luck && Have Fun ! */
const int N = 2e5 + 98;
vector<int> g[N];
int sz[N];
void getsz(int u,int p)
{
    sz[u] = 1;
    for (int v : g[u])
        if (v != p) {
            getsz(v,u);
            sz[u] += sz[v];
        }
}
int fct(int n,int u,int p)
{
    for (int v : g[u])
        if (v != p && sz[v] > n/2)
            return fct(n,v,u);
    return u;
}
ll to[2],cn[2],nu[2],su[2];
void dfs(int u,int p,int d,bool fi=true)
{
    if (fi) {
        for (int i = 0; i < 2; ++i) {
            cn[(d + i) & 1] += nu[i];
            to[(d + i) & 1] += su[i] + nu[i] * d;
        }
    } else {
        ++nu[d&1];
        su[d&1] += d;
    }
    for (int v : g[u])
        if (v != p)
            dfs(v,u,d+1,fi);
}
void DC(int u)
{
    getsz(u,u);
    int n = sz[u];
    u = fct(n,u,u);
    fill_n(nu,2,0);
    fill_n(su,2,0);
    ++nu[0];
    for (int v : g[u]) {
        dfs(v,u,1);
        dfs(v,u,1,false);
    }
    for (int v : g[u]) {
        g[v].erase(find(ALL(g[v]),u));
        DC(v);
    }
}
int main()
{
    RI(n);
    RP(i,n-1) {
        RI(u,v);
        --u,--v;
        g[u].PB(v);
        g[v].PB(u);
    }
    DC(0);
    PL((to[0] + to[1] - cn[1]) / 2 + cn[1]);
}