【luoguP2986】[USACO10MAR]伟大的奶牛聚集Great Cow Gathering

题目链接

先把(1)作为根求每个子树的(size),算出把(1)作为集会点的代价，不难发现把集会点移动到(u)的儿子(v)上后的代价为原代价-(v)的(size)*边权+(总的(size)-(v)的(size))*边权

#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;

const int MAXN=100010;
const int MAXM=200010;

int n,a[MAXN],size[MAXN],dep[MAXN];

int Head[MAXN],num;
struct NODE{
	int to,w,nxt;
} e[MAXM];

inline void add(int x,int y,int z){
	e[++num].to=y;
	e[num].w=z;
	e[num].nxt=Head[x];
	Head[x]=num;
}

void dfs1(int x,int fa){
	size[x]=a[x];
	for(int i=Head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		dep[v]=dep[x]+e[i].w;
		dfs1(v,x);
		size[x]+=size[v];
	}
}

int Ans=1e18;

void dfs2(int x,int fa,int Sum){
	Ans=min(Ans,Sum);
	for(int i=Head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		dfs2(v,x,Sum+e[i].w*(size[1]-2*size[v]));
	}
}

signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	int x,y,z;
	for(int i=1;i<n;++i){
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z); add(y,x,z);
	}
	dfs1(1,0);
	int Sum=0;
	for(int i=1;i<=n;++i)
		Sum+=dep[i]*a[i];
	dfs2(1,0,Sum);
	printf("%lld
",Ans);
	return 0;
}