#include #include using namespace std; vector to[100000]; int main() { int N; cin >> N; for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; a--, b--; to[a].push_back(b); to[b].push_back(a); } vector dpx(N), dpxy(N); auto dfs1 = [&](auto self, int now, int prv) -> void { for (auto nxt : to[now]) { if (nxt != prv) { self(self, nxt, now); dpx[now] += dpx[nxt]; dpxy[now] += dpxy[nxt]; } } dpx[now] += 1; dpxy[now] += dpx[now]; }; dfs1(dfs1, 0, -1); long long ret = 0; auto dfs2 = [&](auto self, int now, int prv, long long dpxpar, long long dpxypar) -> void { ret += dpxy[now] + dpxypar + dpxpar; for (auto nxt : to[now]) { if (nxt != prv) { dpxpar += dpx[nxt]; dpxypar += dpxy[nxt]; } } for (auto nxt : to[now]) { if (nxt != prv) { long long a = dpxpar - dpx[nxt] + 1; long long b = dpxypar - dpxy[nxt] + a; self(self, nxt, now, a, b); } } }; dfs2(dfs2, 0, -1, 0, 0); cout << ret << '\n'; }