Advertisement
TheAnshul

Untitled

Aug 28th, 2018
199
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.65 KB | None | 0 0
  1. /***** TheAnshul *****/
  2.  
  3. #include<bits/stdc++.h>
  4. #define ll long long
  5. #define pb push_back
  6. #define ppb pop_back
  7. #define endl '\n'
  8. #define mii map<ll int,ll int>
  9. #define msi map<string,ll int>
  10. #define mis map<ll int, string>
  11. #define rep(i,a,b) for(ll int i=a;i<b;i++)
  12. #define mpi map<pair<ll int,ll int>,ll int>
  13. #define pii pair<ll int,ll int>
  14. #define vi vector<ll int>
  15. #define vii vector<pair<ll int, ll int>>
  16. #define vs vector<string>
  17. #define all(a) (a).begin(),(a).end()
  18. #define F first
  19. #define S second
  20. #define sz(x) (ll int)x.size()
  21. #define hell 1000000007
  22. #define lbnd lower_bound
  23. #define ubnd upper_bound
  24. #define bs binary_search
  25. #define mp make_pair
  26. #define what_is(x) cerr << #x << " is " << x << endl;
  27. using namespace std;
  28. #define N 200005
  29. vi a[N];
  30. bool vis[N];
  31. ll ans;
  32. ll n;
  33. ll dfs(ll node)
  34. {
  35. ll vl=(n-1)*(n-1),p=0;
  36. vis[node]=1;
  37. for(auto i:a[node])
  38. {
  39. if(!vis[i])
  40. {
  41. ll d;
  42. d=dfs(i);
  43. vl-=d*d;
  44. p+=d;
  45. }
  46. }
  47. // cout<<"*********\n";
  48. // what_is(node);what_is(p);what_is(vl);
  49. // cout<<"*********\n";
  50. vl-=(n-1-p)*(n-1-p);
  51. ans+=(vl/2);
  52. return p+1;
  53. }
  54. int main()
  55. {
  56. ios_base::sync_with_stdio(false);
  57. cin.tie(0);
  58. cout.tie(0);
  59. int TESTS=1;
  60. // cin>>TESTS;
  61. while(TESTS--)
  62. {
  63. cin>>n;
  64. ll x,y;
  65. rep(i,0,n-1)
  66. {
  67. cin>>x>>y;
  68. a[x].pb(y);
  69. a[y].pb(x);
  70. }
  71. dfs(1);
  72. cout<<ans+n*(n-1);
  73. }
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement