题解 | 小O的树上加边

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> col(n + 1, -1);     // 0/1 染色
    queue<int> q;
    col[1] = 0;
    q.push(1);
    long long cnt0 = 1, cnt1 = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) if (col[v] == -1) {
                col[v] = col[u] ^ 1;
                (col[v] ? cnt1 : cnt0)++;
                q.push(v);
            }
    }
    long long ans = cnt0 * cnt1 - (n - 1);
    cout << ans << '\n';
    return 0;
}