[POI2014]FAR-FarmCraft
随手扒拉的一道题 害不错
\(n\)个电脑,管理员送达花费的时间是\(a_i\),管理员只能一个个用户地送电脑。用户安装程序花费的时间是\(b_i\),安排送电脑的顺序,使最晚安装完电脑的用户花费的时间最短
有一个类似国王的游戏的贪心
然后就是一些细节==
统计儿子时要在递归完之后再来统计一遍
int head[N],tot;
struct edge{int v,nxt;}e[N<<1];
void add(int u,int v){
e[++tot]=(edge){v,head[u]},head[u]=tot;
e[++tot]=(edge){u,head[v]},head[v]=tot;
}
int sz[N],son[N];
bool cmp(int x,int y){return sz[x]-f[x]<sz[y]-f[y];}
void dfs(int u,int ff){
if(u!=1) f[u]=a[u];
for(int i=head[u],v;i;i=e[i].nxt) if((v=e[i].v)!=ff) dfs(v,u);
son[0]=0;//sz[u]=1,
for(int i=head[u],v;i;i=e[i].nxt) if((v=e[i].v)!=ff) son[++son[0]]=v;
sort(son+1,son+son[0]+1,cmp);
for(int i=1;i<=son[0];++i) f[u]=Max(f[u],f[son[i]]+sz[u]+1),sz[u]+=sz[son[i]]+2;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
rd(n);
for(int i=1;i<=n;++i) rd(a[i]);
for(int i=1,u,v;i<n;++i) rd(u),rd(v),add(u,v);
dfs(1,0);
printf("%d",Max(f[1],sz[1]+a[1]));
return 0;
}