【BZOJ】1827: [Usaco2010 Mar]gather 奶牛大集会

【算法】树型DP||树的重心（贪心）

【题解】

两遍DFS，第一次得到所有节点子树的路径和，第二次给出除了该子树外其它部分的路径和，时时计算答案。

long long！！！

#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn=100010;
struct edge{int v,w,from;}e[maxn*2];//边数组开大！ 
int first[maxn],tot,size[maxn],n,a[maxn],N;
ll f[maxn],g[maxn],ans;int read()
{char c;int s=0,t=1;while(!isdigit(c=getchar()))if(c=='-')t=-1;do{s=s*10+c-'0';}while(isdigit(c=getchar()));return s*t;
}
void insert(int u,int v,int w)
{tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}
void dfs1(int x,int fa){f[x]=0;size[x]=a[x];for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){dfs1(e[i].v,x);size[x]+=size[e[i].v];g[e[i].v]=f[e[i].v]+1ll*size[e[i].v]*e[i].w;f[x]+=g[e[i].v];}
}
void dfs2(int x,int fa,ll num){ans=min(ans,num+f[x]);for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){dfs2(e[i].v,x,num+f[x]-g[e[i].v]+1ll*(N-size[e[i].v])*e[i].w);}
}int main(){scanf("%d",&n);for(int i=1;i<=n;i++)a[i]=read(),N+=a[i];int u,v,w;for(int i=1;i){u=read();v=read();w=read();insert(u,v,w);insert(v,u,w);}dfs1(1,-1);ans=(1ll<<60);dfs2(1,-1,0);printf("%lld",ans);return 0;
}

令N为所有点权和。

先假设答案点在1，如果存在子树的size（点权和）>N/2，那么就有一半以上的点加边权，另外一些减边权，答案就会增加。

因为size越来越小，所以这样贪心一定正确。

然后这种操作实际上是就是在找树的重心（size算点权），因为树的重心就是满足所有子树size

转载于:https://www.cnblogs.com/onioncyc/p/7454740.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！