Advertisement
yicongli

CF1060E

Jan 21st, 2021 (edited)
374
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.81 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=2e5+7;
  17.  
  18. int n;
  19. ll ans=0;
  20. int siz[N];
  21. int cnt[2];
  22. vector<int>G[N];
  23.  
  24. void dfs(int x,int f,bool d){
  25.     ++cnt[d];
  26.     siz[x]=1;
  27.     for(int i=0;i<G[x].size();++i){
  28.         int v=G[x][i];
  29.         if(v==f)continue;
  30.         dfs(v,x,d^1);
  31.         siz[x]+=siz[v];
  32.     }
  33.     ans+=(ll)siz[x]*(n-siz[x]);
  34. }
  35.  
  36. int main(){
  37.     // freopen(".in","r",stdin);
  38.     // freopen(".out","w",stdout);
  39.     r(n);
  40.     for(int i=1;i<n;++i){
  41.         int u,v;r(u),r(v);
  42.         G[u].push_back(v);
  43.         G[v].push_back(u);
  44.     }
  45.     dfs(1,0,1);
  46.     ans+=(ll)cnt[0]*cnt[1];
  47.     ans>>=1;
  48.     printf("%lld\n",ans);
  49.     return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement