BZOJ_1827_[Usaco2010 Mar]gather 奶牛大集会_树形DP

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);

}