Description：

给定一棵 $N$ 个点的树，求树上一条链使得链的长度乘链上所有点中的最小权值所得的积最大。

$1\le N \le 50000$

Solution：

将点权从大到小排序之后，依次插入这个树之后，我们需要考虑的是经过当前这个点的最长链。稍加思索我们就会发现，这个限制可以放宽为这个森林的最长链，因为如果不经过当前这个点的话，那么之前的答案更优。

假如说我们当前插入了一条边，我们需要维护新的联通块的最长链，性质是，假如我们添加了一条边之后，新的最长链一定是原先 $2$ 个联通块的最长链的端点的一个组合。而 $2$ 个点的距离就是它们 $2$ 个点在原树上的距离，预处理出 $LCA$ 之后可以 $O(logn)$ 查询，有 $6$ 种情况需要讨论，可以用并查集维护一下。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 50010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int v[MAXN],s[MAXN];

int fa[MAXN],top[MAXN],siz[MAXN],dep[MAXN],son[MAXN];

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

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;

}

bool cmp(int x,int y){return v[x] > v[y];}

bool vis[MAXN];

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int l[MAXN],r[MAXN];

int dis(int a,int b){return dep[a] + dep[b] - 2 * dep[LCA(a,b)] + 1;}

void merge(int x,int y)

{

	if(!vis[x] || !vis[y])return;

	x = find(x);y = find(y);

	int a,b,len = 0;

	if(dis(l[x],r[x]) > len){a = l[x];b = r[x];len = dis(l[x],r[x]);}

	if(dis(l[x],l[y]) > len){a = l[x];b = l[y];len = dis(l[x],l[y]);}

	if(dis(l[x],r[y]) > len){a = l[x];b = r[y];len = dis(l[x],r[y]);}

	if(dis(r[x],l[y]) > len){a = r[x];b = l[y];len = dis(r[x],l[y]);}

	if(dis(r[x],r[y]) > len){a = r[x];b = r[y];len = dis(r[x],r[y]);}

	if(dis(l[y],r[y]) > len){a = l[y];b = r[y];len = dis(l[y],r[y]);}

	f[x] = y;

	l[y] = a;r[y] = b;

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&v[i]);

		s[i] = i;f[i] = i;

		l[i] = r[i] = i;

	}

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dfs1(1,1);

	dfs2(1,1);

	sort(s + 1,s + 1 + n,cmp);

	int ans = 0;

	for(int k = 1;k <= n;++k)

	{

		vis[s[k]] = true;

		for(int i = lin[s[k]];i != 0;i = e[i].nxt)

		{

			merge(s[k],e[i].to);

			ans = max(ans,dis(l[find(s[k])],r[find(s[k])]) * v[s[k]]);

		}

	}

	cout << ans << endl;

	return 0;

}