Advertisement
Guest User

Untitled

a guest
Sep 19th, 2017
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = 1e5 + 10;
  4. vector<int>adj[MAX];
  5. int grau[MAX], vstd[MAX];
  6. int cnt[2];
  7. void dfs(int v, int g = 0) {
  8.     grau[v] = g;
  9.     vstd[v] = 1;
  10.     cnt[g]++;
  11.     for(auto u : adj[v]){
  12.         if(!vstd[u]) {
  13.             dfs(u, 1-g);
  14.         }
  15.     }
  16. }
  17. int main() {
  18.     int n, u, v;
  19.     scanf("%d", &n);
  20.     memset(grau, -1, sizeof grau);
  21.     for(int i = 0; i < n-1; ++i){
  22.         scanf("%d %d", &u, &v);
  23.         --u, --v;
  24.         adj[u].push_back(v);
  25.         adj[v].push_back(u);
  26.     }
  27.     dfs(0);
  28.     long long ans = 0;
  29.     for(int i = 0; i < n; ++i){
  30.         if(grau[i] == 1){
  31.             ans+= cnt[0] - adj[i].size();
  32.         }
  33.     }
  34.     printf("%lld\n", ans);
  35.     return 0;
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement