Advertisement
Guest User

Untitled

a guest
Sep 19th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <set>
  6.  
  7. using namespace std;
  8. int n, m;
  9. vector<int> used;
  10. vector<vector<int>> graf;
  11. vector<int> first;
  12. vector<int> second;
  13.  
  14. bool dfs(int v, int color)
  15. {
  16.     if (color == 1)
  17.         first.push_back(v);
  18.     if (color == 2)
  19.         second.push_back(v);
  20.     used[v] = color;
  21.     for (int u: graf[v])
  22.     {
  23.         if (used[u] == 0)
  24.             if (!dfs(u, 3- color))
  25.                     return false;
  26.             else if (used[u] == color)
  27.                     return false;
  28.     }
  29.     return true;
  30. }
  31.  
  32.  
  33.  
  34. int main()
  35. {
  36.     cin >> n;
  37.     used.resize(n, 0);
  38.     graf.resize(n);
  39.     for (int i = 0; i < n - 1; ++i)
  40.     {
  41.         int a, b;
  42.         cin >> a >> b;
  43.         graf[a - 1].push_back(b - 1);
  44.         graf[b - 1].push_back(a - 1);
  45.  
  46.     }
  47.     dfs(0,1);
  48.     int ans = 0;
  49.     int ans2 = 0;
  50.     for (int elem: first)
  51.     {
  52.         ans += second.size() - graf[elem].size();
  53.     }
  54.     cout << ans;
  55.  
  56.  
  57.  
  58.  
  59.  
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement