/////////////////////////////////////////////////////////////////////////////// #include #include #include #include using namespace std; /////////////////////////////////////////////////////////////////////////////// #define DEBUG 0 #define pb push_back #define V vector #define S static #define rep(i,n) for(ll i=0LL; i=0LL; --i) #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(),(a).rend() #define CIN(x) do { \ assert(!cin.eof()); \ cin >> x; \ assert(!cin.fail()); \ } while(0); #if DEBUG #define debug_print(...) _debug_print(__VA_ARGS__) #define debug_printf(...) printf(__VA_ARGS__) #define debug_print_time _debug_print_time #else // DEBUG #define debug_print(...) #define debug_printf(...) #define debug_print_time #endif // DEBUG typedef long long ll; typedef unsigned long long ull; typedef __int128_t ll128; typedef tuple t2; typedef tuple t3; typedef tuple t4; typedef tuple t5; template using priority_queue_incr = priority_queue, greater >; /////////////////////////////////////////////////////////////////////////////// template void incr_m(map &m, TT k) { if (m.find(k) == m.end()) m[k] = 0; m[k]++; } void llin(ll &a) { CIN(a); } void llinl1(V &v, ll count) { for (ll i = 0LL; i < count; ++i) { ll a; CIN(a); v.push_back(a); } } void llinl2(V &v, ll count) { for (ll i = 0LL; i < count; ++i) { ll a, b; CIN(a >> b); v.push_back(t2(a, b)); } } void llinl3(V &v, ll count) { for (ll i = 0LL; i < count; ++i) { ll a, b, c; CIN(a >> b >> c); v.push_back(t3(a, b, c)); } } void llinl4(V &v, ll count) { for (ll i = 0LL; i < count; ++i) { ll a, b, c, d; CIN(a >> b >> c >> d); v.push_back(t4(a, b, c, d)); } } void llina(V &v, ll count) { llinl1(v, count); } template void sort(V &v) { sort(v.begin(), v.end()); } template void sort_reverse(V &v) { sort(v.begin(), v.end(), greater()); } t2 _ext_gcd(ll a, ll b, ll g) { if (!b) return t2(1, 0); ll q = a / b; ll r = a % b; t2 sol = _ext_gcd(b, r, g); ll sx = get<0>(sol); ll sy = get<1>(sol); ll x = sy; ll y = sx - q * sy; return t2(x, y); } t2 ext_gcd(ll a, ll b) { return _ext_gcd(a, b, gcd(a, b)); } // x and mod must be coprime ll mod_inv(ll x, ll mod) { t2 result = ext_gcd(x, mod); ll ret = get<0>(result); while (ret < 0) ret += mod; ret %= mod; return ret; } ll msec() { struct timeval tv; gettimeofday(&tv, NULL); ll ret = 0; ret += tv.tv_sec * 1000LL; ret += tv.tv_usec / 1000LL; return ret; } template void _debug_print(T x) { cout << x << " "; } void _debug_print(const t2 &x) { ll x1 = get<0>(x); ll x2 = get<1>(x); cout << "(" << x1 << ", " << x2 << ") "; } void _debug_print(const t3 &x) { ll x1 = get<0>(x); ll x2 = get<1>(x); ll x3 = get<2>(x); cout << "(" << x1 << ", " << x2 << ", " << x3 << ") "; } void _debug_print(const t4 &x) { ll x1 = get<0>(x); ll x2 = get<1>(x); ll x3 = get<2>(x); ll x4 = get<3>(x); cout << "(" << x1 << ", " << x2 << ", " << x3 << ", " << x4 << ") "; } template void _debug_print(T xarray[], ll n) { rep (i, n) _debug_print(xarray[i]); cout << endl; } template void _debug_print(const V &xlist) { for (auto x : xlist) _debug_print(x); cout << endl; } template void _debug_print(const set &xset) { for (auto x : xset) _debug_print(x); cout << endl; } template void _debug_print(const map &xlist) { for (auto x : xlist) { TT k = x.first; T v = x.second; cout << "K="; _debug_print(k); cout << " V="; _debug_print(v); cout << endl; } } /////////////////////////////////////////////////////////////////////////////// void _main(); int main() { cout << setprecision(12); #if !DEBUG ios::sync_with_stdio(false); cin.tie(0); #endif _main(); return 0; } void make_edgelist(const V &srclist, V edgelist[]) { for (auto src : srclist) { ll a = get<0>(src); ll b = get<1>(src); edgelist[a].pb(b); edgelist[b].pb(a); } } void make_parental_relation(const V edgelist[], ll root, ll n, ll parents[], V children[], ll levels[]) { queue q; bool checked[n+1]; memset(checked, 0, sizeof(checked)); q.push(root); checked[root] = true; parents[root] = root; levels[root] = 0LL; for ( ; !(q.empty()); ) { ll now = q.front(); q.pop(); for (auto next : edgelist[now]) { if (checked[next]) continue; q.push(next); checked[next] = true; parents[next] = now; children[now].pb(next); levels[next] = levels[now] + 1LL; } } } S V edgelist[100010]; S ll parents[100010]; S V children[100010]; S ll levels[100010]; S ll cnts[100010] = {}; ll ans = 0; void dfs(ll v, ll now) { ans += now; for (auto cv : children[v]) { ll orig_cvc = cnts[cv]; ll orig_vc = cnts[v]; cnts[v] -= orig_cvc; cnts[cv] += orig_vc - orig_cvc; dfs(cv, now + orig_vc - orig_cvc * 2LL); cnts[v] += orig_cvc; cnts[cv] -= orig_vc - orig_cvc; } } void _main() { ll n; llin(n); V uvlist; llinl2(uvlist, n-1); make_edgelist(uvlist, edgelist); make_parental_relation(edgelist, 1, n, parents, children, levels); queue q; S ll refs[100010] = {}; srep (v, 1, n+1) refs[v] = children[v].size(); srep (v, 1, n+1) if (!refs[v]) q.push(v); srep (v, 1, n+1) if (!refs[v]) cnts[v] = 1; while (q.size()) { ll v = q.front(); q.pop(); ll pv = parents[v]; if (v == pv) continue; cnts[pv] += cnts[v]; refs[pv]--; if (refs[pv]) continue; q.push(pv); cnts[pv]++; } debug_printf("---- cnts\n"); debug_print(cnts, n+1); ll total = 0; srep (v, 1, n+1) total += cnts[v]; dfs(1, total); debug_printf("---- ans\n"); cout << ans << endl; } ///////////////////////////////////////////////////////////////////////////////