【BZOJ1827】【Vijos1487】【Usaco2010 Mar】奶牛聚会

Author Avatar
q234rty 9月 16, 2017

树形DP即可。

我们定义f(u)=∑v in u's subtreecv×dis(u,v)\displaystyle f(u)=\sum_{v \text{ in }u\text{'s subtree} } c_v \times dis(u,v)，g(u)=∑v isn't in u's subtreecv×dis(u,v)\displaystyle g(u)=\sum_{v \text{ isn't in }u\text{'s subtree} } c_v \times dis(u,v)。

那么 ans=min1≤u≤nf(u)+g(u)\displaystyle ans=\min_{1\le u \le n}f(u)+g(u)。

接下来考虑怎么求ff和gg。

容易发现f(u)=∑v is u's childf(v)+w(u,v)∗sz(v)\displaystyle f(u)=\sum_{v\text{ is }u\text{'s child}}f(v)+w(u,v)*sz(v)，其中sz(u)=∑v in u's subtreecv\displaystyle sz(u)=\sum_{v \text{ in }u\text{'s subtree} } c_v 。

那么g(u)g(u)怎么求呢？考虑从g(fa(u))+f(fa(u))g(fa(u))+f(fa(u))里减去uu的子树的贡献，设sum=∑u=1ncu\displaystyle sum=\sum_{u=1}^{n} c_u，我们有：

g(u)=f(fa(u))+g(fa(u))−f(u)−sz(u)∗w(u,fa(u))+(sum−sz(u))×w(u,fa(u))g(u)=f(fa(u))+g(fa(u))-f(u)-sz(u)*w(u,fa(u))+(sum-sz(u))\times w(u,fa(u))

于是两遍dfs计算szsz、ff和gg就好。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=30000020;
const ll INF=0x3f3f3f3f3f3f3f3fLL;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("1827.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
const int maxn=100001;
struct graph{
    ll sum;
    int n,m;
    struct edge{
        int to,next,cost;
    }e[maxn*2];
    int first[maxn];
    void addedge(int from,int to,int cost){
        e[++m]=(edge){to,first[from],cost};
        first[from]=m;
    }
    bool vis[maxn];
    ll c[maxn],sz[maxn];
    ll f[maxn],g[maxn];
    void dfs(int u){
        sz[u]=c[u];
        vis[u]=1;
        for(int i=first[u];i;i=e[i].next){
            int v=e[i].to;
            if (vis[v])
                continue;
            dfs(v);
            sz[u]+=sz[v];
            f[u]+=f[v]+sz[v]*e[i].cost;
        }
    }
    void dfs2(int u){
        vis[u]=1;
        //printf("%d\n",u);
        for(int i=first[u];i;i=e[i].next){
            int v=e[i].to;
            //printf("%d\n",v);
            if (vis[v])
                continue;
            g[v]=g[u]+f[u]-f[v]-sz[v]*e[i].cost+(sum-sz[v])*e[i].cost;
            dfs2(v);
        }
    }
    ll work(int n){
        for(int i=1;i<=n;i++)
            sum+=c[i];
        dfs(1);
        memset(vis,0,sizeof(vis));
        dfs2(1);
        ll ans=INF;
        for(int i=1;i<=n;i++){
            //printf("%lld %lld %lld\n",sz[i],f[i],g[i]);
            ans=min(ans,f[i]+g[i]);
        }
        return ans;
    }
}g;
int main(){
    init();
    int n=readint();
    for(int i=1;i<=n;i++)
        g.c[i]=readint();
    for(int i=1;i<n;i++){
        int x=readint(),y=readint(),z=readint();
        g.addedge(x,y,z);
        g.addedge(y,x,z);
    }
    printf("%lld",g.work(n));
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2017/09/16/bzoj1827/

隐藏