#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=5e5,M=5e5;
struct node{
	long long d;
	int num;
	node()
	{
		d=0x7f7f7f7f7f7f7f7f;
	}
}d[N];
priority_queue <node> q;
int n,tot,pos,V[N],ver[M],Next[M],head[N],v[N];
long long C[N],edge[M],Size[N],sum,ans,Cn;
bool operator <(const node &a,const node &b)
{
	return a.d>b.d;
}
void add(int x,int y,long long z)
{
	ver[++tot]=y;
	edge[tot]=z;
	Next[tot]=head[x];
	head[x]=tot;
}
void dfs(int x)
{
	v[x]=1,Size[x]=C[x]; //按照奶牛的数量找树的重心
	long long Maxp=0;
	for(int i=head[x];i;i=Next[i])
	{
		int y=ver[i],z=edge[i];
		if(v[y])
			continue;
		dfs(y);
		Size[x]+=Size[y];
		Maxp=max(Maxp,Size[y]);
	}
	Maxp=max(Maxp,Cn-Size[x]);
	if(Maxp<ans)
		ans=Maxp,pos=x;
}
void dijkstra(int k)
{
	d[k].d=0,d[k].num=k;
	q.push(d[k]);
	while(q.size())
	{
		int x=q.top().num;
		q.pop();
		if(V[x])
			continue;
		V[x]=1;
		for(int i=head[x];i;i=Next[i])
		{
			int y=ver[i];
			long long z=edge[i];
			if(d[y].d>d[x].d+z)
			{
				d[y].d=d[x].d+z;
				d[y].num=y;
				q.push(d[y]);
			}
		}
	}
}
int main()
{
	ans=0x7f7f7f7f7f7f7f7f;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&C[i]),Cn+=C[i];
   // Cn 是奶牛的总数
	for(int i=1,x,y;i<n;i++)
	{
		long long z;
		scanf("%d %d %lld",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	dfs(1);
	dijkstra(pos);
	for(int i=1;i<=n;i++)
		sum=sum+d[i].d*C[i];
	printf("%lld",sum);
	return 0;
}

$RT$

做法 : 我按照奶牛的数量找树的重心 , 找到后再进行一遍 Dijkstra , 然后就莫名其妙 AC 了 , 蒟蒻甚是疑惑 。