Bài B - Codeforces Round #435 (Div.2)

Bài B:
Đề bài: Mahmoud và Ehab tiếp tục việc khám phá của họ ! Khi mọi người ở vùng đất quỹ dữ đều biết, Dr. Evil thích đồ thị lưỡng cực, đặc biệt là cây.
  Cây là một đồ thị có chu trình được kết nối. Đồ thị lưỡng cực là một đồ thị, mà các đỉnh của chúng có thể được chia thành 2 phần theo một cách nào đó, mà mỗi cạnh (u,v) thuộc về đồ thị, u và v thuộc về hai tập khác nhau. Bạn có thể tìm nhiều định nghĩa chính thức hơn của một cây và đồ thị lưỡng cực trong các phần được chú thích dưới đây.
 Dr.Evil cho Mahmoud và Ehab một cây bao gồm n đỉnh và hỏi họ rằng thêm các cạnh vào nó bằng một cách nào đó, mà đồ thị vẫn là đồ thị lưỡng cực. Bên cạnh đó, sau khi thêm các cạnh , đồ thị trở nên đơn giản (không chứa khuyên và các cạnh song song). Tìm số cạnh tối đa có thể thêm vào?
 Khuyên là một cạnh, mà kết nối một đỉnh với chính nó. Đồ thị không chứa cạnh song song khi với mỗi cặp đỉnh không có nhiều hơn một cạnh giữa chúng. Một chu trình và khuyên không giống nhau.
Đầu vào:
+ Dòng đầu tiên chứa số nguyên n - số đỉnh của một cây (1<=n<=10^5).
+ n-1 dòng tiếp theo chứa hai số nguyên u và v (1<=u,v<=n,u#v) - mô tả các cạnh của cây.
Đảm bảo rằng đồ thị đã cho là cây.
Đầu ra:
In ra một số nguyên - là số cạnh tối đa mà Mahmoud và Ehab có thể thêm vào cây trong khi vẫn đáp ứng (fulfilling) các điều kiện.
Ví dụ:
Đầu vào:
3
1 2
1 3
Đầu ra:
0
/**/
Đầu vào:
5
1 2
2 3
3 4
4 5
Đầu ra:
2
/**/
Chú thích:
Định nghĩa cây: Wiki (tree definition)
Định nghĩa đồ thị hai phía (bipartite graph definition)
Ở test case đầu tiên, chỉ có một cạnh có thể được thêm bằng một cách nào đó, đồ thị sẽ không chứa khuyên hoặc cạnh song song là (2,3), nhưng việc thêm sẽ làm cho đồ thị mất đi tính lưỡng cực nên kết quả là 0.
Ở test case thứ 2, Mahmoud và Ehab có thể thêm các cạnh (1,4) và (2,5).
Hướng dẫn:
Cây bản thân nó đã mang tính lưỡng cực vì vậy chúng ta chạy dfs để chia cây này thành hai tập (gọi là nhị sắc (bicoloring)). Chúng ta không thể thêm bất kì cạnh nào giữa hai đỉnh cùng một tập và chúng ta có thể thêm 1 cạnh giữa hai đỉnh của hai tập khác nhau,vì vậy gọi số đỉnh của tập bên trái là l và số đỉnh của tập bên phải là r thì số cạnh tối đa có thể tồn tại là l*r, nhưng n-1 cạnh đã tồn tại vì vậy số cạnh lớn nhất được thêm vào là l*r-(n-1).
Độ phức tạp: O(n).
Lời giải:

#include <bits/stdc++.h>

using namespace std;
typedef long long nagai;

vector<vector<int>> g;

int cnt0 = 0;

void d(int u, int p, bool c)
{
 if (c == 0)
  ++cnt0;
 for (int v : g[u])
  if (v != p)
   d(v, u, c ^ 1);
}

int main()
{
 int n;
 cin >> n;
 g.resize(n);
 for (int i = 0; i < n - 1; ++i)
 {
  int a, b;
  cin >> a >> b;
  --a, --b;
  g[a].push_back(b);
  g[b].push_back(a);
 }
 d(0, -1, 0);
 cout << 1LL * cnt0 * (n - cnt0) - (n - 1) << endl;
}