本蒟蒻又卡题了！！

问题讨论区 普及段
86 
#include <iostream>
#include <vector>
#include <cstring>
#include <climits>
using namespace std;


const int N = 105;
vector<int> a[N];
int w[N], dep[N];
int sum[N];
int tot;
int minn = 0;

void dfs(int u, int parent) {
	dep[u] = dep[parent] + 1; // 记录深度 
	
	sum[u] = w[u]; 
	for (int v : a[u]) {
		if (v == parent) continue; 
		dfs(v, u);

		sum[u] += sum[v];
	}
}

void f(int u, int parent, int ans) { // ans: 父亲节点的答案 
	int now = ans;
	if (u != 1) now = now - sum[u] + (tot - sum[u]); // 近了 sum[u] 减掉，远了 tot-sum[u] 加上 
	minn = min(ans, minn); // 取 min 
	for (int v : a[u]) {
		if (v != parent) {
			f(v, u, now);
		}
	}
}

int main() {
	int n;
	cin >> n; 
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
		tot += w[i]; 
	}

	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}

	dfs(1, 0); // 以 0 作无父亲 方便 dep[0] 可以访问 
	for (int i = 1; i <= n; ++i) minn += w[i] * (dep[i]-1); // 以 1 为根，且深度从0开始要-1
	f(1, -1, minn);

	cout << minn << endl;

	return 0;
}
4 个赞
87

谢谢，膜拜大佬%%

3 个赞
88

让我理解一下

4 个赞
90

666

4 个赞