#include #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--) #define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++) #define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--) #define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++) #define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++) #define ALL(x) x.begin(), x.end() using ll = long long; using namespace std; ll dpf(vector> &tree, vector &dp, int now, int bf) { ll res = 1; for(auto nx : tree.at(now)) { if(nx == bf) continue; res += dpf(tree, dp, nx, now); } return dp.at(now) = res; } void dfs(vector> &tree, vector &dp, int now, int bf, ll &ans, ll &sum) { for(auto nx : tree.at(now)) { if(nx == bf) continue; ll nxdp = dp.at(now); ll nowdp = dp.at(now) - dp.at(nx); ll pnxdp = dp.at(nx); ll pnowdp = dp.at(now); ll d = (nxdp + nowdp) - (dp.at(now) + dp.at(nx)); sum += d; ans += sum; dp.at(now) = nowdp; dp.at(nx) = nxdp; dfs(tree, dp, nx, now, ans, sum); sum -= d; dp.at(now) = pnowdp; dp.at(nx) = pnxdp; } } int main() { int n; cin >> n; vector> tree(n, vector()); rep(i, n-1){ int a, b; cin >> a >> b; a--; b--; tree.at(a).push_back(b); tree.at(b).push_back(a); } vector dp(n, 0); dpf(tree, dp, 0, -1); ll sum = accumulate(ALL(dp), 0LL); ll ans = sum; dfs(tree, dp, 0, -1, ans, sum); cout << ans << endl; return 0; }