题目描述
某市有 $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;
}