Guest User

Untitled

a guest
Sep 19th, 2017
1,338
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int lev[100005];
  6. vector<int> adj[100005];
  7. int n;
  8.  
  9. void dfs(int x,int hi,int pa)
  10. {
  11.     int i;
  12.     lev[x]=hi;
  13.     for(i=0;i<adj[x].size();i++)
  14.     {
  15.         if(adj[x][i]==pa)
  16.             continue;
  17.         dfs(adj[x][i],hi+1,x);
  18.     }
  19. }
  20.  
  21. int main()
  22. {
  23.     cin >> n;
  24.     int i;
  25.     for(i=0;i<n-1;i++)
  26.     {
  27.         int x,y;
  28.         cin >> x >> y;
  29.         adj[x].push_back(y);
  30.         adj[y].push_back(x);
  31.     }
  32.     dfs(1,0,-1);
  33.     long long odd=0;
  34.     for(i=1;i<=n;i++)
  35.         odd+=(lev[i]%2);
  36.     cout << odd*(n-odd)-(n-1) << endl;
  37. }
RAW Paste Data