Codeforces Round #435 (Div. 2) 862B. Mahmoud and Ehab and the bipartiteness Solution

   

Problem Link: https://codeforces.com/contest/862/problem/B

Solution in C++:

1. /// La ilaha illellahu muhammadur rasulullah
2. ///******Bismillahir-Rahmanir-Rahim******///
3. /// Abul Hasnat Tonmoy
4. /// Department of CSE,23rd batch
5. /// Islamic University,Bangladesh
6. ///**********ALLAH IS ALMIGHTY************///
7. #include <bits/stdc++.h>
8. using namespace std;
9. const int N = 1e5 + 2;
10. vector<int> g[N];
11. bool vis[N];
12. int col[N];
13. long long l = 0, r = 0;
14. void dfs(int u) {
15. vis[u] = true;
16. for (auto v : g[u]) {
17. if (!vis[v]) {
18. col[v] = col[u] ^ 1;
19. if (col[v] == 1)
20. l++;
21. else
22. r++;
23. dfs(v);
24. }
25. }
26. }
27. int main() {
28. ios_base::sync_with_stdio(0);
29. cin.tie(0);
30. long long n, m;
31. cin >> n;
32. m = n - 1;
33. while (m--) {
34. int u, v;
35. cin >> u >> v;
36. g[u].push_back(v);
37. g[v].push_back(u);
38. }
39. dfs(1);
40. cout << ((r + 1) * l) - (n - 1) << endl;
41. }