API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jun 24th, 2018
90
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.01 KB | None | 0 0
raw download clone embed print report
  1. /**
  2. Polina
  3. ,;;: ,,. ,.sssriisi ,.; SS555s322XXrr;,;::;;;rsSsr93hhhhhhhh9hX5X5sXis:...
  4. .:::;r: :...:;;rsii5 , .s:52S2sSrs5222iSs;,;:;.;:sirs:hhh9993h9hhGh9X5Ss,,:i Ss.
  5. ,,;:;r ;s; . . . ,r; r;s;;iS5:.;;S322Sr;;:::;;:rs;s;ih99X5hhhhGh99X;:,rr5Si;s::
  6. ::;;:, ,r . ;S, s,,iirirs;:s5523h;;;r.rs,:,,r;iir9hhX99GhhhhXss;;;23X22Sr;:.
  7. ;;r;:. ir ;, :srrriisSS99hh9hh9GG,;,r5;r,,;;,39hh9hG99hGhh99srsXhhX92S5SisS
  8. ;:;rrs:, , . . .. ,;.,i:ssrii;5S95;9h9hhhhG9hSh. S,;;,:G9hX23hhGhh3995i5Xh932i52s55SS
  9. :;,;;rrss: i5i ., ,,, ::;; .i;s;22;;sX3h9h9hh9hh:hh 3s;GiGh9X9r535hGh95XX9Gh3399XX5sis;.
  10. . , :,,::r;ssr.Sis . .::;.sr52 ,,;SS5SssiiS2S399993hhhhhhhhGGGhhh953hhhhh99XX3GGG9h599S5rSsr5
  11. ,., ,,: ,,:s:;rsSSSii . .,:,;SSsisr rr;rr;;;;:;rsS5X33999hhhhhGhGGG&2h9X39Xh9hhh9G&Gh3GGG9i55SSsS..
  12. ....,,,. ..rs,sr;iiiss r rs,:;rsr::...,.,,.,,,,:;ssS5X3999hhhhhhGG:XGG39X9h9GGGGGGG39G&Gh25iS5SsS,.... .
  13. . .. ;rs :srssrssr;r ;sss;:, ..,:;riSXX399h9hhGhhGGG&,h939h&&&GGG&&GGGGh9XSS5Ss,,,,.....:
  14. .... ;r ;s;;;r::::::;,:. ..,,;riS5333hhhhhGGGGG&G&X2hSGhGGG&&G&hhGiiS5225srsSSSS2X33
  15. ,:; ;; ,;;;;::,:.::: ..,::;i55339hhhhGGGGGGGGG99h933G&&GGG&&G55533SS9h99999993X
  16. ,::, :;;;,,.:. ..,:;rsS5339hhhhGGGGGGh3293h&GG&&&&&GGGSG3Shhh93XX3X33X2;
  17. .,.,. .:;;;;,. . .,,:;rsS5399hhGhGGGhGGGGhXhhG&&&&GGGG&GGGh9352SXr:r9332
  18. ,:;;;:,,,. ..,:;;ss593XhhhGGGGG&&G33hG&G&&&&&h&GG&G3h99h353XiX993:
  19. ... ,,.;,,::.. ,,,,::;rri2h93GhGGGGGGGhX99G9&&&&&G&G&&h9h5hh3h9h35sh992
  20. . . . .:,. ...,,:;;;riS5X9h9GhGGGG&G&GhGG&&&&&&&&GG&G9G3s2323322sh933
  21. . ,,.. .,::::;si22X392393hhGG&G&&&&&&G&&&&&&GGGhhG9X29h395srr9993
  22. ... ..:;;s222XX2XSSi2999hG&G&G&&&G&h&&G&&G&&GGhG9XG3hX2ssrr2hh9
  23. .... ..,:rssiS555iiiSS2X3hhhhGGGGG&&&h&&&&&&GG&GGGGGG932Ssssrihh3
  24. ,,,... .,:;rsiS5555XhhGhGh39hhhhGGG&GG&&&G&&&&&&&GGGG39X2Xh5sssshh9
  25. ,:;rsisssirs;:,,,. .,:riS52239GG399rs5XX9hhGGGGGG&GGh&&&&GG&GGG99352SSsSisiiXhh
  26. ,;siSSSSsssr;:,,,,. .:;i52XXX3h933X9sri223hhhhGGGG&G&&&G&GGGG&GGh9332255SiiisShh
  27. ..;rsrrrrssisrrrrr;,. ..;i2X3X233i393r:;S2329hhhhhGGG&GG&GG&&&G&GGGh33X3S55SSSSSGh
  28. .r;iSS2333X3X55Sissr: .rs2332s3X5SssiSX2339S9h99hhGGh&GGGG&G&GGGGGG999XX255iS52Gh
  29. .rs5X39335X, ,;siisr;: ,sSX335issssissS522XXX9939hGGGGGGGGGGGGGGGGGh999hh9h&GGGGG
  30. si2X3X33XX:..,ri;r, , .:i5X3X5irrsrsrssiSsi593933hhGG&GGGGG&&GGGGGGGhGhGhhGGhGh3
  31. siSX2XX53i:;r;s;:;,.. ,;52225Ssr;r;rrrrrrrr29X339hGGGGG&h&G&GGGGGGGGG39XSSS5255
  32. , . rsiSS2XX225iis:,,, . .;S52255ir;:::;:::;:;sX9399hGGGGG&GG&G&GGGGGGGh9993X2XX55
  33. .;rriiS55Siisr;,,.. :s55252Sir;:,,,.:,::;sX939hhhGGGG&&G&&&&GGGGGGh399222225
  34. ;;sssiSSSissr;,,. . ,rS22225Ss;::,,.,,::;sS3999hhGG&GGG&GG&&&GGGGhGh939X22X2
  35. ;;iisiSSSisr;::.. ,rs2XX2XSsr:,....,,:rsS5999GhGGGGGGGGGG&&&GGGGhh939XX222
  36. s ri2iSSSiisr;:,.. ;s52XX33S;;,...,,:;;iS2X99hGhGGGGGG&&&G&&&GGGGGh999X322
  37. ;;sSXiSSSiir;;,,... :;S5XXXX35r,,,.,:;;riS233h3hGhGGG&GG&&G&&&&GGGGh9h933XX
  38. ss2XXS55Sis;;:,.. :s5222232i:,,.,,;rrS5X3999hhhGGGG&G&GG&GG&GGGGGG9h933X
  39. ,. : ;; :ri2233S5Sisr;,.. .;S55S5532ir,,,,:;rS52X9h39hG9GGGGGGGG&GGG&&GGGGGGhh33X
  40. .,:;;:r:.. r .r;s22XX325Srr::.. ,;iXX3XX5Sir;;:,;riS2X39h99GhGhGGGGGGGG&&&G&&&GGGGhh933
  41. :,,;:::::;;: . ,rr5X2XXX3SSss;:.. . . ,is;.,;s55X25SSisss;;;rsS523399hGhGhGGhhGGGGGGGG&&&&GGGGhG99h
  42. ,.,:, r;S5X2XX3X3sSsr:,..... ,:rssiiiSiSisisiS52X3399hGG9GGhh9GGGGGGGG&G&G&G&GGGhGG
  43. ,::i55XXXX333;iir:,,... ..,:riiiS5S5issS522XX39hGhGG3hGhGhGGG&&GGG&G&GGGGGGGGG
  44. .,;sS5X5XX3333X,iis;:,,.. ...,r5555XGh35SSS22XX399hG&99hGh9GhGGG&&&G&&&GGGGGGGGG
  45. ,;s;s5222XXX33X3:;ss;;:,,,,,,. .. ,;S5X339X3X255SSS2XX399h&hX99hh9GhhGGG&&&&&&&G&GGGGGG
  46. .:;Sii5252XXX3X33Xr;rrr;:::;ss5SiS2SiiiSii5S22255255222X339hGG&X939hhhG9XGGG&G&&&G&&GGGGGG
  47. ;;S iS2252XX333XX9rrrrr;r;rss;:;:,..,,;rrrsSS22225222X339hhGGG9hhGGGhGGGhGG&G&G&&&&&&G&GG
  48. .:.:55siS5222233333333rssr;rrrr::.. ,,:rrsiSS552X222XX39hhGGhGhGhGhGG3G&hhGG&GG&&&G&&&G&&
  49. ssr,Ss:;SXS2XXX33933939ssssr;;;::,,,;rss;rriiSS5S2X2XX39hhhGhhhhGhGGhGGh&GGh&GG&&&&&GGGGG&
  50. ,:sr .iiiiS2222XXX33333999hSis;;::::::,.,::;rrssiiS52XX33hhhhhGGhhGG&9Ghhh&X&hGGG&GG&&&GG&GG
  51. ..,::;r,i;si5252X2X93339399hhhhsr;;:,.. .,:;;rrsiiSS52XX999h9hhhG93GhhGGGh&&G3G&GG&&&&&&&&G&&
  52. r s:,SiSSi552XX2X33399999hhhhGir;:,,,:::;;rssiiiS52X399999hhhhGX9G9G3GGh&GGGhGGG&&G&&G&&&&
  53. .. r:,r.is;r5sS25525X33339hhh9hhhhhh9s;::;:;rsrssiS55XXX33333999hhG2S99G9G&GhGG&GGG&&&G&&G&&&G
  54. :r,; :, s srr ;iriii5552X2X339999hhhhhhhh9932irrissS5552522XXXXXX333399GhSS9hG9G&hGGGGGG&&&&&&G&&&&
  55. .:;r;r;.;: ,..: ;r,;;sriri5SXX2X33999939hhhhhhh93X225255S55555555522XXXX9999hGXSXhGGG&&GGGhGGGG&&&&&&&&&
  56. ;;:.::.: , ;,s:s s;s:sSs553XXX333999999hhhhh9333X55555SSSSSSS5522222X33339hG9299Gh&G&&GGGG&&G&&&&&&GG
  57. . ,, i..:,,;;s;srS5S2XXX333993933hhhh999332255555555SSS55552222333339GG3X9GG&&&G&GGGG&GG&&&&&G&
  58. . ,:;.;,;rs:rSiS533333339393999hh99333X2255SSSiSS5255555552X39333GGGh39GG&GGGGGG&&&&&&&&&&&
  59. :..s. :,;;;;rrisSXSXX3333939X3h99999333XX225555SSSSS5S555555399999hGGGh9G&G&G&GGG&G&G&&&&&&&
  60. :.,; ;;:,:r;;rsSSXXX33339332399hh99333XX22522255SSSS5SSSSS5X393939399939hGGh&&GG&&&&&&&&&&
  61. **/
  62. #define _FORTIFY_SOURCE 0
  63. #pragma GCC optimize("Ofast")
  64. #pragma GCC optimize("no-stack-protector")
  65. #pragma GCC optimize("unroll-loops")
  66. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  67. #pragma GCC optimize("fast-math")
  68. #include <iostream>
  69. #include <string>
  70. #include <stdio.h>
  71. #include <vector>
  72. #include <set>
  73. #include <unordered_set>
  74. #include <map>
  75. #include <unordered_map>
  76. #include <deque>
  77. #include <algorithm>
  78. #include <math.h>
  79. #include <time.h>
  80. #include <random>
  81. #define ff first
  82. #define ss second
  83. #define pb push_back
  84. #define mp make_pair
  85. #define int long long
  86. #define double long double
  87. #define left left228
  88. #define right right228
  89. #define x1 x1228
  90. #define y1 y1228
  91. #define all(x) x.begin(), x.end()
  92. #define rand() (rand() << 15 | rand())
  93.  
  94. using namespace std;
  95.  
  96. typedef long long ll;
  97. typedef pair<int, int> pii;
  98. mt19937 randint(1423434);
  99.  
  100. const int maxn = 3e5 + 7, mod = 1e9 + 7, inf = 1e18;
  101. const double eps = 1e-9, pi = acos(-1);
  102. int n, ans = -inf;
  103. int block[maxn], pr[maxn], siz[maxn], cnt[maxn];
  104. vector<int> gr[maxn], cd[maxn];
  105. vector<pii> vertex[maxn];
  106.  
  107. int dfs(int u, int pr1) {
  108. int cur = 0;
  109. for (auto v : gr[u]) {
  110. if (block[v] == 0 && v != pr1) cur += dfs(v, u);
  111. }
  112. return siz[u] = cur + 1;
  113. }
  114.  
  115. int centroid(int u, int pr1, int sz) {
  116. for (auto v : gr[u]) {
  117. if (v == pr1 || block[v]) continue;
  118. if (siz[v] > sz / 2) return centroid(v, u, sz);
  119. }
  120. return u;
  121. }
  122. void lenght(int u, int pr1, int deep, int start) {
  123. if (u == -1) return;
  124. vertex[start].pb({cnt[u], deep});
  125. for (auto v : gr[u]) {
  126. if (block[v] || v == pr1) continue;
  127. lenght(v, u, deep + 1, start);
  128. }
  129. }
  130.  
  131. int divide(int u) {
  132. dfs(u, u);
  133. int u1 = centroid(u, u, siz[u]);
  134. lenght(u, u, 1, u1);
  135. u = u1;
  136. block[u] = 1;
  137. for (auto v : gr[u]) {
  138. if (block[v] == 0) cd[u].pb(divide(v));
  139. }
  140. return u;
  141. }
  142.  
  143. int len = 1;
  144. vector<int> tree;
  145.  
  146. void build(int sz) {
  147. len = 1;
  148. while (len < sz) len <<= 1;
  149. tree.assign(len + len - 1, 0);
  150. }
  151.  
  152. int get(int l, int r, int l1, int r1, int root) {
  153. if (l >= l1 && r <= r1) return tree[root];
  154. else if (max(l, l1) > min(r, r1)) return 0;
  155. else {
  156. int tm = (l + r) / 2;
  157. return max(get(l, tm, l1, r1, root * 2 + 1), get(tm + 1, r, l1, r1, root * 2 + 2));
  158. }
  159. }
  160.  
  161. void upd(int l, int r, int l1, int r1, int root, int x) {
  162. if (l >= l1 && r <= r1) tree[root] = max(tree[root], x);
  163. else if (max(l, l1) > min(r, r1)) return;
  164. else {
  165. int tm = (l + r) / 2;
  166. upd(l, tm, l1, r1, root * 2 + 1, x);
  167. upd(tm + 1, r, l1, r1, root * 2 + 2, x);
  168. tree[root] = max(tree[root * 2 + 1], tree[root * 2 + 2]);
  169. }
  170. }
  171.  
  172. void get_path(int pp, vector<int> &root) {
  173. vector<int> x;
  174. for (auto v : root) {
  175. for (auto u : vertex[v]) {
  176. x.pb(u.ff);
  177. }
  178. }
  179. sort(all(x));
  180. x.erase(unique(all(x)), x.end());
  181. build(x.size());
  182. for (auto v : root) {
  183. for (auto u : vertex[v]) {
  184. int id = lower_bound(all(x), u.ff) - x.begin();
  185. int val = u.ss + get(0, len - 1, id, len - 1, 0);
  186. ans = max(ans, val * u.ff);
  187. ans = max(ans, min(pp, u.ff) * u.ss);
  188. }
  189. for (auto u : vertex[v]) {
  190. int id = lower_bound(all(x), u.ff) - x.begin();
  191. upd(0, len - 1, id, id, 0, u.ss);
  192. }
  193. }
  194. }
  195.  
  196. void mult(int rt) {
  197. vector<int> root;
  198. for (auto v : cd[rt]) root.pb(v);
  199. get_path(cnt[rt], root);
  200. reverse(all(root));
  201. get_path(cnt[rt], root);
  202. }
  203.  
  204. void solve() {
  205. cin >> n;
  206. for (int i = 0; i < n; ++i) cin >> cnt[i];
  207. for (int i = 0; i < n - 1; ++i) {
  208. int a, b; cin >> a >> b;
  209. --a, --b;
  210. gr[a].pb(b);
  211. gr[b].pb(a);
  212. }
  213. divide(0);
  214. for (int i = 0; i < n; ++i) {
  215. mult(i);
  216. }
  217. cout << ans;
  218. }
  219.  
  220. signed main() {
  221. // freopen("check.in", "r", stdin);
  222. // freopen("check.out", "w", stdout);
  223. #ifdef offline_judge
  224. freopen("TASK.in", "r", stdin);
  225. freopen("TASK.out", "w", stdout);
  226. #endif
  227. srand(228);
  228. cout.precision(10);
  229. cout << fixed;
  230. ios_base::sync_with_stdio(false);
  231. cin.tie(0);
  232. solve();
  233. return 0;
  234. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!