题意：
分析：
- 前置芝士：通道 (可能会做通道的人，也用不着看题解了)
我们利用做通道时的结论:
在一颗边权均为正的树上，存在两个点集
对于一个点集 (s) 它的直径两端是 (a,b)
对于另一个点集 (t) 它的直径两端是 (c,d)
那么分别以 (s) 和 (t) 点集中的点为直径的两端，这条直径一定是 ((a,c),(a,d),（b,c),(b,d)), 中的一条
然后我们就可以通过树剖预处理做到(O(log)) 得到两个连通块合并后的直径
然后我们就按照点权从大向小枚举 (u) 和 (u) 的出边，然后合并两个并查集，顺便在合并时更新一下 (ans)
tip:
枚举 (u) 的出边时要保证 (v) 的点权比 (u) 大，因为大的点不会对 (v[u]) 产生影响，我们更新的时候默认点权是 (u) 的连通块的最小点权，因为 大的点权不会对小的点权产生影响
- 另解
边分治
首先多叉转二叉（三度化），然后在一侧枚举一条边，在另一侧中找出权值比它大的最长链，更新答案
递归下去，复杂度 (O(nlog ))
代码：
不会边分治/kk，只有并查集的代码
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
using namespace std;
namespace zzc
{
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 5e4+5;
int n,cnt;
int head[maxn],siz[maxn],v[maxn],p[maxn],son[maxn],fa[maxn],top[maxn],dep[maxn];
long long ans=0;
vector<int> g[maxn];
struct edge
{
int to,nxt;
}e[maxn<<1];
void add(int u,int v)
{
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
bool cmp(int x,int y)
{
return v[x]>v[y];
}
void dfs1(int u,int ff)
{
siz[u]=1;son[u]=0;fa[u]=ff;dep[u]=dep[ff]+1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==ff) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void dfs2(int u,int bel)
{
top[u]=bel;
if(son[u]) dfs2(son[u],bel);
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
int calc(int x,int y)
{
return dep[x]+dep[y]-(dep[lca(x,y)]<<1);
}
struct node
{
int x,y,dis;
node(){x=0,y=0,dis=0;}
node(const int &_x,const int &_y){x=_x,y=_y,dis=calc(_x,_y);}
node(const int &_x,const int &_y,const int &_dis){x=_x,y=_y,dis=_dis;}
}dp[maxn];
bool operator <(node a,node b)
{
return a.dis<b.dis;
}
node operator + (node a,node b)
{
if(!a.x) return b;
if(!b.x) return a;
node res=max(a,b);
res=max(res,max(max(max(node(a.x,b.y),node(a.y,b.x)),node(a.x,b.x)),node(a.y,b.y)));
return res;
}
struct dsu
{
int fa,val,siz;
}f[maxn];
int find(int x)
{
return f[x].fa==x?x:f[x].fa=find(f[x].fa);
}
void merge(int x,int y)
{
int fx=find(x),fy=find(y);
if(f[fx].siz<f[fy].siz) swap(fx,fy);
f[fy].fa=fx;
f[fx].val=min(f[fx].val,f[fy].val);
dp[fx]=dp[fx]+dp[fy];
ans=max(ans,1ll*(dp[fx].dis+1)*f[fx].val);
}
void work()
{
int a,b;
n=read();
for(int i=1;i<=n;i++) v[i]=read();
for(int i=1;i<n;i++)
{
a=read();b=read();
if(v[a]>v[b]) swap(a,b);
g[a].pb(b);
add(a,b);add(b,a);
}
dfs1(1,0);dfs2(1,1);
for(int i=1;i<=n;i++) p[i]=i,f[i].fa=i,f[i].val=v[i],f[i].siz=1,dp[i]=node(i,i,0);
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;i++) for(auto v:g[p[i]]) merge(p[i],v);
printf("%lld
",ans);
}
}
int main()
{
zzc::work();
return 0;
}