时间限制
500 ms
内存限制
64 MB

题解 ：

• 注意到 树本身就是二分图（一层为黑，一层为白…）；现在需要加一条原先不存在的边使得还是一张二分图，只能在黑层和白层之间连一条边，还要减去原先存在的边（n-1）

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;int n;
vector<int> G[N];
ll odd = 0, even = 0;void dfs(int u, int fa, int cur) {if (cur % 2) odd ++ ;else even ++ ;for (auto v : G[u]) {if (v != fa) {dfs(v, u, cur + 1);}}
}int main() {cin >> n;for (int i = 0; i < n - 1; ++ i) {int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}dfs(1, -1, 1);cout << odd * even - (n - 1);
}