#include #include using namespace std; using Graph = vector>; vector depth; vector subtree_size; vector count_; int N; void dfs(const Graph& G, int v, int p, int d) { depth[v] = d; for (auto nv : G[v]) { if (nv == p) continue; dfs(G, nv, v, d + 1); } subtree_size[v] = 1; for (auto c : G[v]) { if (c == p) continue; subtree_size[v] += subtree_size[c]; } } void dfs2(const Graph& G, int v, int p) { if (v != 0) count_[v] = count_[p] + N - 2 * subtree_size[v]; for (auto nv : G[v]) { if (nv == p) continue; dfs2(G, nv, v); } } int main() { cin >> N; Graph G(N); for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; G[a - 1].push_back(b - 1); G[b - 1].push_back(a - 1); } depth.assign(N, 0); subtree_size.assign(N, 0); count_.assign(N, 0); dfs(G, 0, -1, 0); for (int i = 0; i < N; i++) { count_[0] += subtree_size[i]; } dfs2(G, 0, -1); long long ans = 0; for (int i = 0; i < N; i++) { ans += count_[i]; } cout << ans << endl; }