https://www.luogu.com.cn/record/88838671

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5005;
ll siz[N], f[N], g[N][N], d[N], n, m, u, v;
vector<int> G[N];
int dfs1(int u, int fa) {
	for (int v : G[u])
		if (v != fa) siz[u] += dfs1(v, u);
	return siz[u] += 1;
}
ll dfs(int u, int fa) {
	ll sum = 0x3f3f3f3f3f3f3f3f;
	g[u][0] = 0;
	for (int v : G[u]) {
		if (v == fa) continue;
		dfs(v, u);
		for (int i = siz[u]; i >= siz[v] - 1; i --)
			g[u][i] = min(g[u][i], g[u][i - siz[v] + 1] + f[v]);
	}
	for (int i = 0; i < siz[u]; i ++)
		sum = min(sum, g[u][i] + d[siz[u] - i]);
	return f[u] = sum;
}
int main() {
	cin >> n;
	memset(g, 0x3f, sizeof g);
	for (int i = 2; i <= n; i ++)
		cin >> d[i];
	for (int i = 1; i < n; i ++) {
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1, 0);
	cout << dfs(1, 0) << '\n';
	return 0;
}