USACO 2010 Mar Gold 1.Great Cow Gathering 树形dp

事实证明，人类的脑残是没有极限的 他的意思就是简单的要死的动规题 即使你已经搞出了动态转移方程也会只拿70分

原题：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个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和，(比如，农场i到达农场X的距离是20，那么总路程就是C_i*20)。帮助Bessie找出最方便的地点来举行大集会。

首先 这一看就是一道简单的树形DP

对于百分之50的数据

我们可以枚举根，进行转移

我们可以用f[i]表示第i个节点及其子树全部挪到i点时的最小花费，用size[i]表示其本身及其子树共有多少人。容易得到方程

size[i]=∑size[j]+size[i]j∈son[i]f[i]=∑(f[j]+size[j]∗val[j])j∈son[i]

这就是正常的50分做法。

对于100分算法，我们可以发现，其实真正的耗时的地方在于对于每一个点都要进行O(n)的验证，显然这是十分缓慢的，容易发现，从一个节点到其他的儿子进行跟的转移，只需要将中间的边进行处理。

我们可以用g[i]表示以i为根所需要的最小价值，那么容易得到

g[x]=g[fa]+(sum−2∗size[x])∗(val)x∈son[fa]

所以两次DFS就可以了

下面是代码

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define N 100000+5
#define M 200000+5
using namespace std;
long long ans=ll;
int head[N],n,a[N],size[N];
long long f[N];
bool vis[N];
long long g[N];
struct graph
{
    int next,to;
    long long val;
    graph (){}
    graph (int _next,int _to,int _val)
    :next(_next),to(_to),val(_val){}
}edge[M];
struct point
{
    int x;
    int val;
    bool operator<(const point &z)const
    {
        return val<z.val;
    }
}P[N];
inline void add(int x,int y,int z)
{
    static int cnt = ;
    edge[++cnt]=graph(head[x],y,z);
    head[x]=cnt;
    edge[++cnt]=graph(head[y],x,z);
    head[y]=cnt;
}
inline int read()
{
    int x = , f = ; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x *  + ch - '0'; ch = getchar(); }
    return x * f;
}
bool flag=false;
long long sum;
void DFS(int x,int fa)
{
    size[x]=a[x];
    f[x]=;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to^fa)
        {
            DFS(edge[i].to,x);
            size[x]+=size[edge[i].to];
            f[x]+=(long long)size[edge[i].to]*(long long)edge[i].val+f[edge[i].to];
        }
}
void reDFS(int x,int fa,int val)
{
    if(x!=)
        g[x]=g[fa]+(sum-*size[x])*(val);
    else
        g[x]=f[x];
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to^fa)
            reDFS(edge[i].to,x,edge[i].val);
}
int main()
{
    freopen("meet.in", "r", stdin);
    freopen("meet.out", "w", stdout);
    cin>>n;
    for(int i=;i<=n;++i)
        a[i]=read(),P[i].x=i,P[i].val=a[i];
    for(int i=;i<n;++i)
    {
        int tmp1=read(),tmp2=read(),tmp3=read();
        add(tmp1,tmp2,tmp3);
    }
    DFS(,-);
    ans=f[];
    sum=size[];
    reDFS(,-,);
    sort(g+,g+n+);
    cout<<g[];
}