E60 树形DP+贪心 P3574 [POI2014] FAR-FarmCraft

视频链接：

 

 

 

P3574 [POI2014] FAR-FarmCraft - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 树形DP+贪心 O(nlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N=500005;
int head[N],to[N<<1],ne[N<<1],idx;
void add(int x,int y){to[++idx]=y,ne[idx]=head[x],head[x]=idx;
}
int n,a[N],f[N],s[N],p[N];bool cmp(int x,int y){return f[x]-s[x]>f[y]-s[y];
}
void dfs(int x,int fa){f[x]=a[x];for(int i=head[x];i;i=ne[i])if(to[i]!=fa) dfs(to[i],x);int t=0;for(int i=head[x];i;i=ne[i])if(to[i]!=fa) p[++t]=to[i];sort(p+1,p+t+1,cmp);for(int i=1;i<=t;++i){f[x]=max(f[x],s[x]+1+f[p[i]]);s[x]+=s[p[i]]+2;}
}
int main(){scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]);for(int i=1,x,y;i<n;++i)scanf("%d%d",&x,&y),add(x,y),add(y,x);dfs(1,0);printf("%d\n",max(f[1],s[1]+a[1]));
}