bzoj 1827: [Usaco2010 Mar]gather 奶牛大集會

→題目連結←

【想說的話】

沒有什麼想說的=.=

周末沒什麼事不刷題感覺不太好

【題解】

兩遍dfs（樹形dp）

将點1當作根

第一遍dfs計算出每個點子節點總數，還有将它作為集會地點時它的子樹中的點滿足條件需要的代價

第二遍計算出答案，點1的答案就是dfs1時處理出的代價，剩下的點的答案就對于它與它父親節點的那條邊計算一下就好

具體看代碼吧

【代碼】

#include<bits/stdc++.h>

#define MAXN 100010
#define ll long long
#define inf 1000000000

using namespace std;

inline int rd(){
	int x=0,y=1;char c=getchar();
	while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x*y;
}

struct node{
	int to,len;
	node(int x,int y){to=x,len=y;}
};

int n;
vector<node>v[MAXN];
int a[MAXN],fa[MAXN];
ll ans[MAXN],sum[MAXN],num[MAXN];
ll tot=0;

inline void link(int x,int y,int z){
	v[x].push_back(node(y,z));
	v[y].push_back(node(x,z));
}

void dfs1(int x){
	num[x]=a[x];
	sum[x]=0;
	for(int i=0; i<v[x].size(); i++){
		int to=v[x][i].to;
		int len=v[x][i].len;
		if(to==fa[x])continue;
		fa[to]=x;
		dfs1(to);
		num[x]+=num[to];
		sum[x]+=sum[to]+num[to]*len;
	}
}

void dfs2(int x,int len){
	if(!fa[x])ans[x]=sum[x];
	else ans[x]=ans[fa[x]]-num[x]*len+(tot-num[x])*len;
	for(int i=0; i<v[x].size(); i++){
		int to=v[x][i].to;
		int len=v[x][i].len;
		if(fa[x]==to)continue;
		dfs2(to,len);
	}
}

int main(){
	memset(fa,0,sizeof(fa));
	n=rd();
	for(int i=1; i<=n; i++)a[i]=rd(),tot+=a[i];
	for(int i=1; i<n; i++){
		int x=rd(),y=rd(),z=rd();
		link(x,y,z);
	}
	dfs1(1);
	dfs2(1,0);
	ll Min=(ll)inf*(ll)inf;
	for(int i=1; i<=n; i++)Min=min(Min,ans[i]);
	printf("%lld\n",Min);
	
	return 0;
}