题解 P2986 【[USACO10MAR]伟大的奶牛聚集Great Cow Gat…】
xfydemx
2018-08-14 16:11:28
一类经典的树形dp问题。
考虑 f[i] 表达以i为根子树中奶牛到i的距离和。
第一次dfs从下至上递推出各点的 f[i] 和子树奶牛数 siz[i]
画图易知每个点的答案 d[i] 满足的方程
```cpp
d[v] = d[u] - siz[v]*a[i].w + (cnt - siz[v])*a[i].w;
```
通过第二次dfs推得各点的 d[i]
显然最小的 d[i] 即为答案
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cctype>
#include<cmath>
#define ll long long
using namespace std;
const int N = 1000005;
const ll INF = 1e55;
inline int read() {
int s = 1, w= 0; char c = getchar();
for(; !isdigit(c); c=getchar()) if(c=='-') s = -1;
for(; isdigit(c); c=getchar()) w = 10*w+c-'0';
return s*w;
}
ll m,n,ans=INF,cnt,inde,head[N],siz[N],c[N],f[N],d[N];
struct Edge{
ll nxt,to,w;
}a[N];
inline void add(int x,int y,int w){
a[++inde].to=y;
a[inde].nxt=head[x];
a[inde].w=w;
head[x]=inde;
}
inline void dfs (int u, int fa) {
siz[u] = c[u];
for(int i = head[u]; i; i = a[i].nxt) {
int v = a[i].to;
if(v == fa) continue;
dfs(v,u);
siz[u] += siz[v];
f[u] = f[u] + f[v] + siz[v] * a[i].w;
}
}
inline void dp (int u, int fa) {
for(int i = head[u]; i; i = a[i].nxt) {
int v = a[i].to;
if(v == fa) continue;
d[v] = 1LL*d[u] - siz[v]*a[i].w + (cnt - siz[v])*a[i].w;
ans = min(ans, d[v]);
dp(v,u);
}
}
int main() {
int u,v,w;
n = read();
for(int i=1; i<=n; i++){
c[i]=read();
cnt += c[i];
}
for(int j=1; j<n; j++){
u = read(); v = read(); w=read();
add(u,v,w);
add(v,u,w);
}
dfs(1,0);
d[1]=f[1];
ans = min(ans, d[1]);
dp(1,0);
printf("%lld\n", ans*1LL);
return 0;
}
```