Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <string>
- #include <set>
- using namespace std;
- int n, m;
- vector<int> used;
- vector<vector<int>> graf;
- vector<int> first;
- vector<int> second;
- bool dfs(int v, int color)
- {
- if (color == 1)
- first.push_back(v);
- if (color == 2)
- second.push_back(v);
- used[v] = color;
- for (int u: graf[v])
- {
- if (used[u] == 0)
- if (!dfs(u, 3- color))
- return false;
- else if (used[u] == color)
- return false;
- }
- return true;
- }
- int main()
- {
- cin >> n;
- used.resize(n, 0);
- graf.resize(n);
- for (int i = 0; i < n - 1; ++i)
- {
- int a, b;
- cin >> a >> b;
- graf[a - 1].push_back(b - 1);
- graf[b - 1].push_back(a - 1);
- }
- dfs(0,1);
- int ans = 0;
- int ans2 = 0;
- for (int elem: first)
- {
- ans += second.size() - graf[elem].size();
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement