题意：
给定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; }