1 /**************************************************************  2     Problem: 2870  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:1032 ms  7     Memory:6596 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 using namespace std; 14 typedef long long ll; 15 const int N = 50005; 16   17 struct edge { 18     int next, to; 19     edge() {} 20     edge(int _n, int _t) : next(_n), to(_t) {} 21 } e[N << 1]; 22 int first[N], tot; 23   24 struct data { 25     int l, v; 26     data() {} 27     data(int _l, int _v) : l(_l), v(_v) {} 28       29     inline bool operator < (const data &x) const { 30         return l < x.l; 31     } 32 } t1[N], t2[N]; 33 int cnt_t1, cnt_t2; 34   35 struct tree_node { 36     int sz, w, vis; 37 } tr[N]; 38   39 ll ans; 40 int n, now; 41 int q1[N], q2[N], top1, top2; 42   43 inline int read() { 44     int x = 0; 45     char ch = getchar(); 46     while (ch < ‘0‘ || ‘9‘ < ch) 47         ch = getchar(); 48     while (‘0‘ <= ch && ch <= ‘9‘) { 49         x = x * 10 + ch - ‘0‘; 50         ch = getchar(); 51     } 52     return x; 53 } 54   55 inline void Add_Edges(int x, int y) { 56     e[++tot] = edge(first[x], y), first[x] = tot; 57     e[++tot] = edge(first[y], x), first[y] = tot; 58 } 59   60 int Maxsz, Root; 61   62 void dfs(int p, int fa, int sz) { 63     int x, y, maxsz = 0; 64     tr[p].sz = 1; 65     for (x = first[p]; x; x = e[x].next) 66         if ((y = e[x].to) != fa && !tr[y].vis) { 67             dfs(y, p, sz); 68             tr[p].sz += tr[y].sz; 69             maxsz = max(maxsz, tr[y].sz); 70         } 71     maxsz = max(maxsz, sz - tr[p].sz); 72     if (maxsz < Maxsz) 73         Root = p, Maxsz = maxsz; 74 } 75   76 int find_root(int p, int sz) { 77     Maxsz = N << 1; 78     dfs(p, 0, sz); 79     return Root; 80 } 81   82 void count_sz(int p, int fa) { 83     int x, y; 84     tr[p].sz = 1; 85     for (x = first[p]; x; x = e[x].next) 86         if ((y = e[x].to) != fa && !tr[y].vis) { 87             count_sz(y, p); 88             tr[p].sz += tr[y].sz; 89         } 90 } 91   92 void count1(int p, int fa, int len, int v) { 93     int x, y; 94     t1[++cnt_t1] = data(len, v); 95     for (x = first[p]; x; x = e[x].next) 96         if ((y = e[x].to) != fa && !tr[y].vis) 97             count1(y, p, len + 1, min(v, tr[y].w)); 98 } 99  100 void count2(int p, int fa, int len, int v) {101     int x, y;102     t2[++cnt_t2] = data(len, v);103     for (x = first[p]; x; x = e[x].next)104         if ((y = e[x].to) != fa && !tr[y].vis)105             count2(y, p, len + 1, min(v, tr[y].w));106 }107  108 void count(int p, int first_p) {109     int x, y;110     t1[++cnt_t1] = data(1, tr[p].w);111     for (x = first[p]; x != first_p; x = e[x].next)112         if (!tr[y = e[x].to].vis)113             count1(y, p, 2, min(tr[p].w, tr[y].w));114     t2[++cnt_t2] = data(1, tr[p].w);115     for (x = first_p; x; x = e[x].next)116         if (!tr[y = e[x].to].vis)117             count2(y, p, 2, min(tr[p].w, tr[y].w));118 }119  120 void work(int p, int cnt_p) {121     int root = find_root(p, cnt_p), sz1 = 0, sz2 = 0, tmp;122     int x, y, first_root, i, l1, l2;123     count_sz(root, 0);124     for (x = first[root]; x; x = e[x].next)125         if (!tr[y = e[x].to].vis) {126             sz1 += tr[y].sz;127             if (sz1 + 1 << 1 >= tr[root].sz) {128                 first_root = e[x].next;129                 sz2 = tr[root].sz - (sz1++);130                 break;131             }132         }133     cnt_t1 = cnt_t2 = 0;134     count(root, first_root);135      136     sort(t1 + 1, t1 + cnt_t1 + 1), sort(t2 + 1, t2 + cnt_t2 + 1);137     for (i = 1, top1 = 0; i <= cnt_t1; ++i) {138         while (top1 && t1[i].v > t1[q1[top1]].v) --top1;139         q1[++top1] = i;140     }141     for (i = 1, top2 = 0; i <= cnt_t2; ++i) {142         while (top2 && t2[i].v > t2[q2[top2]].v) --top2;143         q2[++top2] = i;144     }145      146     for (l1 = 1, l2 = 0; l1 <= top1; ++l1) {147         while (l2 < top2 && t2[q2[l2 + 1]].v >= t1[q1[l1]].v) ++l2;148         ans = max(ans, (ll) (t1[q1[l1]].l + t2[q2[l2]].l - 1) * t1[q1[l1]].v);149     }150     for (l1 = 0, l2 = 1; l2 <= top2; ++l2) {151         while (l1 < top1 && t1[q1[l1 + 1]].v >= t2[q2[l2]].v) ++l1;152         ans = max(ans, (ll) (t1[q1[l1]].l + t2[q2[l2]].l - 1) * t2[q2[l2]].v);153     }154      155     tmp = ++now;156     if (sz2 - 1 >= 2) {157         for (x = first[root]; x != first_root; x = e[x].next)158             if (!tr[y = e[x].to].vis)159                 tr[y].vis = now;160         work(root, sz2);161         for (x = first[root]; x != first_root; x = e[x].next)162             if (tr[y = e[x].to].vis == tmp)163                 tr[y].vis = 0;164     }165     tmp = ++now;166     if (sz1 - 1 >= 2) {167         for (x = first_root; x; x = e[x].next)168             if (!tr[y = e[x].to].vis)169                 tr[y].vis = now;170         work(root, sz1);171         for (x = first_root; x; x = e[x].next)172             if (tr[y = e[x].to].vis == tmp)173                 tr[y].vis = 0;174     }175 }176  177 int main() {178     int i;179     n = read();180     for (i = 1; i <= n; ++i)181         tr[i].w = read();182     for (i = 1; i < n; ++i)183         Add_Edges(read(), read());184     work(1, n);185     printf("%lld\n", ans);186     return 0;187 }