sacgajcvs

Untitled

Oct 6th, 2020
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.83 KB | None | 0 0
  1. /*
  2. _____ _ _ _ _
  3. |_ _| |__ ___ / \ _ __ ___| |__ _ _| |
  4. | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  5. | | | | | | __// ___ \| | | \__ \ | | | |_| | |
  6. |_| |_| |_|\___/_/ \_\_| |_|___/_| |_|\__,_|_|
  7.  
  8. */
  9. #include<bits/stdc++.h>
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. #include <ext/pb_ds/tree_policy.hpp>
  12. #define ll int
  13. #define pb push_back
  14. #define ppb pop_back
  15. #define endl '\n'
  16. #define mii map<ll,ll>
  17. #define msi map<string,ll>
  18. #define mis map<ll, string>
  19. #define rep(i,a,b) for(ll i=a;i<b;i++)
  20. #define repr(i,a,b) for(ll i=b-1;i>=a;i--)
  21. #define trav(a, x) for(auto& a : x)
  22. #define pii pair<ll,ll>
  23. #define vi vector<ll>
  24. #define vii vector<pair<ll, ll>>
  25. #define vs vector<string>
  26. #define all(a) (a).begin(),(a).end()
  27. #define F first
  28. #define S second
  29. #define sz(x) (ll)x.size()
  30. #define hell 1000000007
  31. #define lbnd lower_bound
  32. #define ubnd upper_bound
  33. #define max(a,b) (a>b?a:b)
  34. #define min(a,b) (a<b?a:b)
  35.  
  36. /* For Debugging */
  37. #define DEBUG cerr<<"\n>>>I'm Here<<<\n"<<endl;
  38. #define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
  39. #define what_is(x) cerr << #x << " is " << x << endl;
  40.  
  41. std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
  42. #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
  43. #define TIME cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
  44. #define DECIMAL(n) cout << fixed ; cout << setprecision(n);
  45. #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  46. using namespace __gnu_pbds;
  47. using namespace std;
  48. #define PI 3.141592653589793
  49. #define N 100005
  50. vi a[N];
  51. ll par[N],maxHeight[N],maxPath[N],ans[N];
  52.  
  53.  
  54. void fun(ll node,ll height,ll path) {
  55. vii tmp1,tmp2;
  56.  
  57. tmp1.pb({height,-1});
  58. tmp2.pb({path,-1});
  59.  
  60. for(auto i : a[node]) {
  61. if(i != par[node]) {
  62. tmp1.pb({maxHeight[i],i});
  63. tmp2.pb({maxPath[i],i});
  64. }
  65. }
  66.  
  67. sort(all(tmp1));
  68. sort(all(tmp2));
  69. reverse(all(tmp1));
  70. reverse(all(tmp2));
  71.  
  72.  
  73. auto find_best_height = [&] (vi v) {
  74. set<ll> st;
  75. for(auto i:v) {
  76. st.insert(i);
  77. }
  78.  
  79. trav(j,tmp1) {
  80. if(st.find(j.S)==st.end()) {
  81. return j.F;
  82. }
  83. }
  84. return 0;
  85. };
  86.  
  87. auto find_best_two_height = [&] (ll i) {
  88. if(sz(tmp1)<=2) {
  89. return -2;
  90. }
  91. ll sum = 0,cnt = 2;
  92. trav(j,tmp1) {
  93. if(j.S!=i) {
  94. sum+=j.F;
  95. cnt--;
  96. if(cnt==0) {
  97. return sum;
  98. }
  99. }
  100. }
  101. return -2;
  102. };
  103.  
  104.  
  105. auto find_best_path = [&] (vi v) {
  106. set<ll> st;
  107. for(auto i:v) {
  108. st.insert(i);
  109. }
  110.  
  111. trav(j,tmp2) {
  112. if(st.find(j.S)==st.end()) {
  113. return j.F;
  114. }
  115. }
  116. return 0;
  117. };
  118.  
  119.  
  120.  
  121. for(auto i : a[node]) {
  122. if(i != par[node]) {
  123. fun(i,find_best_height({i}), max(find_best_two_height(i) + 2, find_best_path({i})));
  124. }
  125. }
  126.  
  127. ans[node] = 0;
  128.  
  129. for(auto i : tmp2) {
  130. ans[node] = max(ans[node],i.F * (find_best_two_height(i.S) + 2) );
  131. }
  132.  
  133. // for(auto i:a[node]) {
  134. // if(i!=par[node]) {
  135. // ans[node] = max(ans[node],(height + maxHeight[i] + 2) * find_best_path({i,-1}));
  136. // }
  137. // }
  138.  
  139. }
  140.  
  141. void precalc(ll node) {
  142. vi tmp;
  143. for(auto i : a[node]) {
  144. if(par[node] != i) {
  145. par[i] = node;
  146. precalc(i);
  147. tmp.pb(-maxHeight[i]);
  148. maxHeight[node] = maxHeight[i] + 1;
  149. maxPath[node] = max(maxPath[node],maxPath[i]);
  150. }
  151. }
  152. if(sz(tmp) > 1) {
  153. sort(all(tmp));
  154. maxPath[node] = max(maxPath[node],-(tmp[0]+tmp[1]));
  155. }
  156. return;
  157. }
  158.  
  159. void solve()
  160. {
  161. ll n,x,y;
  162. cin>>n;
  163. rep(i,1,n) {
  164. cin>>x>>y;
  165. a[x].pb(y);
  166. a[y].pb(x);
  167. }
  168. par[1] = -1;
  169. precalc(1);
  170. fun(1,0,0);
  171. ll pans=0;
  172. rep(i,1,n+1) {
  173. pans=max(pans,ans[i]);
  174. }
  175. cout<<pans<<endl;
  176. return;
  177. }
  178. int main()
  179. {
  180. FAST
  181. int TESTS=1;
  182. // cin>>TESTS;
  183. rep(i,0,TESTS)
  184. {
  185. // cout<<"Case #"<<i+1<<": ";
  186. solve();
  187. }
  188. TIME
  189. return 0;
  190. }
Advertisement
Add Comment
Please, Sign In to add comment