P2986 [USACO10MAR] Great Cow Gathering G
一道转移类型的树形dp
考虑u点作为集合地点，不方便度为f，如果换做v点（v为u的一个儿子），不方便度会怎么变化
pre[u]表示在u点上方的点值之和，sum[u]表示u点子树点值之和
如果换做v点
f+(pre[u]+sum[u]-sum[v])w-sum[v]w
pre[u]+sum[u]-sum[v]表示这个边一头所有的点值之和
sum[v]表示这个边另一头所有的点值之和
所以问题变为了维护sum数组和pre数组
点击查看代码
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e5+5;
ll ans;
int cnt,head[maxn];
struct node{
int to,next,w;
}edg[maxn];
void add(int u,int v,int w){
edg[++cnt].next=head[u];head[u]=cnt;edg[cnt].to=v;edg[cnt].w=w;
}
int n;
ll val[maxn],dep[maxn],sum[maxn],pre[maxn];
void dfs1(int u,int fa);
void dfs2(int u,int fa,ll f);
int main(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&val[i]);
for(int aa,bb,ww,i=2;i<=n;i++){
scanf("%d%d%d",&aa,&bb,&ww);
add(aa,bb,ww);add(bb,aa,ww);
}
dfs1(1,0);
for(int i=2;i<=n;i++)
ans+=val[i]*dep[i];
dfs2(1,1,ans);
printf("%lld\n",ans);
return 0;
}
void dfs1(int u,int fa){
sum[u]=val[u];
for(int i=head[u];i;i=edg[i].next){
int to=edg[i].to,w=edg[i].w;
if(to==fa)continue;
dep[to]=dep[u]+w;
dfs1(to,u);
sum[u]+=sum[to];
}
}
void dfs2(int u,int fa,ll f){
pre[u]=pre[fa]+sum[fa]-sum[u];
for(int i=head[u];i;i=edg[i].next){
int to=edg[i].to,w=edg[i].w;
if(to==fa)continue;
ans=min(ans,f+(pre[u]+sum[u]-sum[to])*w-sum[to]*w);
dfs2(to,u,f+(pre[u]+sum[u]-sum[to])*w-sum[to]*w);
}
}