HDU 3899 求所有人移動到某點的最小距離和 樹形dp

題意：

給定n個點

每個點的人數

n-1條邊和邊權。

選取任意一點u，然後讓所有人都移動到u點

問最小的移動距離和是多少

水dp

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
#include
#include
using namespace std;
#define mod 112233
#define N 100030
#define ll __int64
struct Edge{
	ll from, to, nex, dis;
}edge[N*2];
ll head[N], edgenum;
void add(ll u, ll v, ll dis){
	Edge E={u,v,head[u],dis};
	edge[edgenum] = E;
	head[u] = edgenum++;
}
ll n;
ll dp[N], siz[N]; //i的子樹到i的花費， siz[i]為i子樹下隊伍數量
ll T[N], all;
void dfs(ll u, ll fa){
	dp[u] = 0;	siz[u] = T[u];
	for(ll i = head[u]; ~i; i = edge[i].nex)
	{
		ll v = edge[i].to;  if(v==fa)continue;
		dfs(v,u);
		dp[u] += siz[v]*edge[i].dis + dp[v];
		siz[u] += siz[v];
	}
}
ll hehe[N];//i點的花費
void doubi(ll u, ll fa){
	for(ll i = head[u]; ~i; i = edge[i].nex){
		ll v = edge[i].to; if(v==fa)continue;
		ll dis = edge[i].dis;
		hehe[v] = hehe[u] - siz[v]*dis + (all-siz[v])*dis;
		doubi(v,u);
	}
}
ll ans;
void init(){memset(head, -1, sizeof head); edgenum = 0 ;}
int main(){
	ll i, j, u, v, d;
	while(~scanf("%I64d",&n)){
		init();
		all = 0;
		for(i = 1; i <= n; i++)scanf("%I64d",&T[i]), all+=T[i];
		for(i = 1; i < n; i++){
			scanf("%I64d %I64d %I64d",&u,&v,&d);
			add(u,v,d);
			add(v,u,d);
		}
		dfs(1,1);
		ans = dp[1];
		hehe[1] = dp[1];
		doubi(1,1);
		for(i=2;i<=n;i++)ans = min(ans, hehe[i]);
		printf("%I64d\n",ans);
	}
	return 0;
}