rt，此题 $O(N^{2})$ 做法只跑前 $1000$ 条边可过，代码如下。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct Node{
	int x, w;
};
int n, c, a[N], ans = 1e9, dis[N], dp[N], sum[N], vv, cnt, xx[N], yy[N], vis;
vector<Node> v[N];
void dfs(int x, int fa){
	dp[vv] += dis[x] * a[x];
	sum[x] = a[x];
	cnt += a[x];
	for(Node i : v[x]){
		if(i.x != fa){
			dis[i.x] = dis[x] + i.w;
			dfs(i.x, x);
			sum[x] += sum[i.x];
		}
	}
}
void DFS(int x, int fa){
  vis = min(vis, dp[x]);
	for(Node i : v[x]){
		if(i.x != fa){
			dp[i.x] = dp[x] + (cnt - sum[i.x] - sum[i.x]) * i.w;
			DFS(i.x, x);
		}
	}
}
signed main(){
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;

	for(int i = 1, x, y, z; i < n; i++){
		cin >> x >> y;
		z = 1;
		v[x].push_back({y, z});
		v[y].push_back({x, z});
		xx[i] = x;
		yy[i] = y;
	}
	for(int i = 1; i <= n; i++)cin >> a[i];
  for(int i = 1; i < min(500, n); i++){
    fill(&dp[0], &dp[n] + 1, 0);
    fill(&dis[0], &dis[n] + 1, 0);
    fill(&sum[0], &sum[n] + 1, 0);
    vis = 1e9;
    cnt = 0;
    vv = xx[i];
    dfs(xx[i], yy[i]);
    DFS(xx[i], yy[i]);
    int v2 = vis;
    fill(&dp[0], &dp[n] + 1, 0);
    fill(&dis[0], &dis[n] + 1, 0);
    fill(&sum[0], &sum[n] + 1, 0);
    vis = 1e9;
    cnt = 0;
    vv = yy[i];
    dfs(yy[i], xx[i]);
    DFS(yy[i], xx[i]);
    ans = min(ans, vis + v2);
  }
	cout << ans << '\n';
  return 0;
}