题意：n个地点构成一棵树，第 i 个地点有 t_i 个人，现要选一个地点开会，求所有人行走距离之和的最小值。N<=10^5
分析：先任选一个地点，求出总代价，然后就能求出相邻点的代价，一遍dfs就能求出所有点的代价。
dfs会爆栈，需要开内存挂：#pragma comment(linker, "/STACK:1024000000,1024000000")
View Code #include#include #include using namespace std;#define N 100001#pragma comment(linker, "/STACK:1024000000,1024000000")typedef __int64 LL;int n,t[N],e,sum;int first[N],next[N<<1],v[N<<1],w[N<<1];LL dp[N],tsum[N],ans[N];void init(){ e=sum=0; memset(first,-1,sizeof(first));}void add(int a,int b,int c){ v[e]=b; w[e]=c; next[e]=first[a]; first[a]=e++;}void DP(int a,int fa){ dp[a]=0; tsum[a]=t[a]; int i,b; for(i=first[a];~i;i=next[i]) { b=v[i]; if(b==fa) continue; DP(b,a); tsum[a]+=tsum[b]; dp[a]+=dp[b]+tsum[b]*w[i]; }}void dfs(int a,int fa,LL cost){ int i,b; for(i=first[a];~i;i=next[i]) { b=v[i]; if(b^fa) dfs(b,a,ans[b]=cost+(sum-2*tsum[b])*w[i]); }}int main(){ int a,b,c; while(~scanf("%d",&n)) { init(); for(int i=1;i<=n;i++) { scanf("%d",&t[i]); sum+=t[i]; } for(int i=1;i