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[];
}