BZOJ_1827_[Usaco2010 Mar]gather 奶牛大集会_树形DP
题意：Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在 N(1<=N<=100,000) 个农场中的一个，这些农场由N-1条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1 <= A_i <=N; 1 <= B_i <= N),长度为L_i(1 <= L_i <= 1,000)。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居住者C_i(0 <= C_i <= 1,000)只奶牛。在选择集会的地点的时候，Bessie希望最大化方便的程度(也就是最小化不方便程度)。比如选择第X个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和。
分析：
如果对每个点进行dfs，时间复杂度为O(n^2)。我们可以由父节点递推出子节点。对于这道题而言，我们先假设根节点为1，用一遍dfs维护出每个子树的大小。
再推出以其他点为根节点的答案，时间复杂度是O(n)的。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
#define LL long long
int head[N],to[N<<1],nxt[N<<1],val[N<<1],cnt,n;
LL dis[N],sum[N],ans,niu[N],All,c[N];
inline void add(int u,int v,int w)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
val[cnt]=w;
}
LL dfs1(int x,int y)
{
LL tot=0;
for(int i=head[x];i;i=nxt[i])
{
int t=to[i];
if(t!=y)
{
LL s=dfs1(t,x);
dis[x]+=dis[t]+1ll*val[i]*s;
tot+=s;
}
}
return niu[x]=c[x]+tot;
}
void dfs2(int x,int y)
{
for(int i=head[x];i;i=nxt[i])
{
int t=to[i];
if(t!=y)
{
sum[t]=sum[x]-1ll*niu[t]*val[i]+(All-niu[t])*1ll*val[i];
dfs2(t,x);
}
}
}
int main()
{
ans=1ll<<60;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
All+=c[i];
}
int x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs1(1,0);
sum[1]=dis[1];
ans=sum[1];
dfs2(1,0);
for(int i=2;i<=n;i++)
{
ans=min(ans,sum[i]);
}
printf("%lld",ans);
}