# 题目描述
某市有 $n$ 个县，并有 $n-1$ 条双向高速公路连通这 $n$ 个县，每条高速公路的长度为$1$。受疫情影响，第 $i$ 个县里有 $a_i$ 个患者。为了让疫情较轻的县帮助疫情严重的县，政府决定选择两个县 $x, y$，$x$ 的疫情较为**不**严重，$y$的疫情较为严重（即 $a_x \leq a_y$），并让 $x$ 县 帮助 $y$ 县。县 $x$ 将为县 $y$ 的每一个患者送一份医疗物资，以最短路从 $x$ 到 $y$ 运输，运送一份医疗物资通过长度为 $1$ 的高速公路需要花费 $1$ 元，由政府掏钱报销。请问如果任意选择两个县实施帮扶计划，政府最多要花多少钱？
## 输入描述
第一行，一个正整数 $n$。
第二行，$n$ 个正整数，第 $i$ 个表示 $a_i$。
接下来 $n-1$ 行，每行两个数 $u, v$，表示县 $u$ 和县 $v$ 之间有一条高速公路
## 输出描述
一个数表示答案。
## 样例输入
```
8
3 1 4 1 5 9 2 6
1 2
2 3
2 4
1 5
5 6
4 8
3 7
```
## 样例输出
```
45
```
## 限制及约定
本题采用子任务形式评测。
对于所有数据，满足 $n \leq 50000$, $1 \leq a_i \leq 1000$。
# 题解
偷了官方题解， 写的十分详细，上图。
我写的代码比较丑， 官方给的标程可以去看一下。%%%%%%%OI爷
关于上面结论的论证可以看这篇 $Blog$ [点这里](https://www.cnblogs.com/Khada-Jhin/p/10195287.html)
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> P;
const int MAXN = 3e5 + 5;
const int INF = 0x3f3f3f3f;
vector<int> E[MAXN];
int n, a[MAXN], x[MAXN], y[MAXN], xx;
int ans1;
void dfs(int u, int fa, int dep, int *X){
X[u] = dep;
for(int i = 0;i < E[u].size();i++){
if(E[u][i] == fa)
continue;
dfs(E[u][i], u, dep+1, X);
}
}
void solve() {
cin >> n;
for(int i = 1;i <= n;i++)
cin >> a[i];
for(int i = 1;i < n;i++){
int u, v;
cin >> u >> v;
E[u].push_back(v);
E[v].push_back(u);
}
dfs(1, 0, 0, x);
int xx = 1;
for(int i = 1;i <= n;i++){
if(x[i] > x[xx])
xx = i;
}
memset(x, 0 ,sizeof(x));
dfs(xx, 0, 0, x);
int yy = 1;
for(int i = 1;i <= n;i++){
if(x[i] > x[yy])
yy = i;
}
dfs(yy, 0, 0, y);
int ans = 0;
for(int i = 1;i <= n;i++)
ans = max(ans, max(a[i]*x[i], a[i]*y[i]));
cout << ans << endl;
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(NULL),cout.tie(NULL);
int T;
T = 1;
//cin >> T;
while(T--) {
solve();
}
return 0;
}
```
学军信友队趣味网络邀请赛 B. 齐心抗疫
