题解 P2986 【[USACO10MAR]伟大的奶牛聚集Great Cow Gat…】

· · 题解

一类经典的树形dp问题。

考虑 f[i] 表达以i为根子树中奶牛到i的距离和。

第一次dfs从下至上递推出各点的 f[i] 和子树奶牛数 siz[i]

画图易知每个点的答案 d[i] 满足的方程 

d[v] = d[u] - siz[v]*a[i].w + (cnt - siz[v])*a[i].w;

通过第二次dfs推得各点的 d[i]

显然最小的 d[i] 即为答案 

#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;
}