[USACO2010 Mar Gold 【gather】]树形dp

【题目链接】http://ace.delos.com/ioiupload?init=1&a=uNRSh9JKRlk
【题目大意】
就是给一颗树，树上的点都有不同数目的奶牛。
然后边有边权。
让你选一个结点，使得所有牛到这个点走的路程之和最小。
【算法分析】
随便拿个点做根。
两次DFS。
第一次算出两个信息：
1、以该结点为根的子树上的牛的总数目。
2、该结点的子孙到该点的距离之和。
第二次算出另一个信息：
从父亲来的那部分需要的距离之和。
最后将两部分相加即可。
【其它】1Y。
【CODE】
/*
ID:jie22221
TASK:gather
LANG:C++
*/
#include #include #include #include using namespace std;
typedef long long lld;
const int N=105555;
struct edge{int x,y,w;edge *next;}*ls[N];
int n;
int c[N];
lld f[N],cow[N],From_Fa[N],ans=(lld)(1) << 60; void addedge(int x,int y,int w){
edge *t=(edge *)malloc(sizeof(edge));
t->x=x; t->y=y; t->w=w; t->next=ls[x]; ls[x]=t;
}

void init(){
ios::sync_with_stdio(false);
cin >> n;
for (int i=1;i<=n;i++) cin >> c[i];
for (int i=1,x,y,w;i cin >> x >> y >> w;
addedge(x,y,w);
addedge(y,x,w);
}
}

void predfs(int p,int fa){
cow[p]=c[p];
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa){
predfs(t->y,p);
f[p]+=cow[t->y]*t->w+f[t->y];
cow[p]+=cow[t->y];
}
}

void dfs(int p,int fa){
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa){
From_Fa[t->y]=From_Fa[p]+f[p]-f[t->y]-cow[t->y]*t->w+(cow[1]-cow[t->y])*t->w;
dfs(t->y,p);
}
ans=min(ans,From_Fa[p]+f[p]);
}

int main(){
freopen("gather.in","r",stdin);
freopen("gather.out","w",stdout);
init();
predfs(1,0);
dfs(1,0);
cout << ans << endl;
return 0;
}