拆除前哨站1
需积分: 0 8 浏览量
2022-08-08
18:47:06
上传
评论
收藏 19KB DOCX 举报
128MB,2S,outpost.xxx
拆除前哨站
问题描述
位于特斯拉城的前哨站为新伦敦贡献了很多的蒸汽核心。随着天边直冲云霄
的风暴铺天盖地地袭来，必须从现在开始将前哨站的设备拆除，距离最后撤离还
有 N 个小时，恰好有 N 个设备（编号 1 到 N）需要拆除，每个设备需要耗费 1
小时的时间才能拆除，这些设备构成一棵以 1 号设备为根的有根树，一个节点能
够被拆除当且仅当其没有未被拆除的儿子节点。
但是为了抵御暴风雪，即使正在撤离，也要尽可能地生产，每个节点有一个
生产效率 pi（可能是负数），在其开始被拆除之前，每小时会贡献值为 pi 的生
产值。现在新伦敦的领袖想知道拆除期间的生产值之和最大是多少，同时他还想
知道字典序最小的方案是什么。
选手可以自行开启 O2。
输入描述
第一行一个整数 N
第二行 N 个整数 pi
接下来 N-1 行，每行 2 个整数 u v 表示 u 号设备与 v 号设备构成父子关系（具
体关系由根节点推出）。
输出描述
一行一个整数，表示拆除期间的生产值之和的最大值。
一行 N 个整数，第 i 个表示第 i 个拆除的设备。
样例输入
【样例一】
5
-1 -1 -2 -2 -1
评论0