题目描述

某市有 $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$ 点这里

代码

#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;
}