思路：

设f[i][j]表示当前i节点的子树，有j个是ave + 1的最小代价
转移方程就是$f[x][j]=min(f[x][j-k]+f[y][k]+abs(s[y]-(size[y]-k)\ast val-k\ast (val+1ll))\ast b[i].w)$
其中y是儿子，x是当前节点，s[y]是儿子子树的油桶数的数量，size[y]是儿子子树的大小，val是平均值，k是给儿子多少个val + 1

$code$

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>

#define ll long long

using namespace std;

ll t, val, SIZE;
ll n, sum, size[110], s[110];
ll a[110], f[110][110];
ll tot, head[110], g[110];
struct node {
    
	ll to, next, w;
}b[10010];

void add(ll x, ll y, ll z) {
    
	b[++ tot] = (node) {
     y, head[x], z };
	head[x] = tot;
}

ll min(ll x, ll y) {
     return x < y ? x : y; }

void dfs(ll x, ll fa) {
    
	size[x] = 1, s[x] = a[x];
	f[x][0] = f[x][1] = 0;
	for(ll i = head[x]; i; i = b[i].next) {
    
		ll y = b[i].to;
		if(fa == y) continue;
		dfs(y, x);
	}
	for(ll i = head[x]; i; i = b[i].next) {
    
		ll y = b[i].to;
		if(y == fa) continue;
		memset(g, 0x7f7f7f7f, sizeof(g));
		s[x] += s[y], size[x] += size[y];
		for(ll j = 0; j <= size[x] && j <= SIZE; j ++)
			for(ll k = 0; k <= j && k <= size[y]; k ++)
				g[j] = min(g[j], f[x][j - k] + f[y][k] + abs(s[y] - (size[y] - k) * val - k * (val + 1ll)) * b[i].w);
		for(ll j = 0; j <= SIZE && j <= size[x]; j ++)
			f[x][j] = g[j];
	}
}

int main() {
    
	scanf("%lld", &t);
	while(t --) {
    
		scanf("%lld", &n);
		for(ll i = 1; i <= n; i ++) {
    
			scanf("%lld", &a[i]);
			sum += a[i];
		}
		val = sum / n, SIZE = sum % n;
		for(ll i = 1; i < n; i ++) {
    
			ll x, y, z;
			scanf("%lld%lld%lld", &x, &y, &z);
			add(x, y, z), add(y, x, z);
		}
		memset(f, 0x7f7f7f7f, sizeof(f));
		dfs(1, 0);
		printf("%lld\n", f[1][SIZE]);
		memset(head, 0, sizeof(head));
		memset(s, 0, sizeof(s));
		memset(size, 0, sizeof(size));
		sum = 0;
	}
	return 0;
}