一艘飞船正在太阳系执行任务，途中遭遇太阳风暴。飞船呈长条状，有 n 个节点分别装着价值为 v [］的设备。节点之间有 n -1个连接道路，道路长 d []，且该道路不受太阳风暴影响。 有一种护盾，能够保护半径为 k 的范围不受风暴影响，且飞船上载有 s 个该护盾。 现求安放多少个护盾（<= s )，分别在哪些节点上，才能保护价值最多的设备，且保证节点之间是连接的（节点之间道路不必完全在护盾范围里，但两个节点之间的节点如果被破坏，就不算作连接的节点，即不能只保护断开的，价值高的节点）。 输入格式： 第一行3个整数，表示 n 个节点， s 个护盾，护盾半径为 k 。 第二行 n -1个整数，第 i 个整数表示第 i 个节点到第 i +1个节点的距离。第三行 n 个整数，表示节点的价值。 输出格式： 第一行1个整数 x ，表示安放几个盾牌。 第二行 x 个整数，表示盾牌安放在第几个节点。数据范围： 总范围：1<= s <= n <=10^6 1<= k <=10^12 1<= d [ i ]<=10^6(1<= i <= n -1) 1<= v [ i ]<=10^6(1<= i <= n -1)

思路：二分答案+树形DP

题目要求我们在保护价值最大的设备的前提下，安放最少的护盾，那么显然这个最大的设备就是我们二分答案的目标。

我们二分答案mid，然后考虑在这个价值大于等于mid的设备中，如何安放护盾可以使得连接这些设备的路径数量最少。

我们考虑一条路径p，其中有一个设备的价值大于等于mid，那么我们可以在这个设备周围放置护盾，保护这条路径。那么问题就转化为了如何选择一些设备，使得它们的范围内可以覆盖所有的路径。

我们考虑树形DP，设f[i]表示以i为根节点，且i的子树内选取的一些设备的范围可以覆盖i到其它节点的路径的最小数量。同时，我们需要记录子树内选取的设备的价值和sum[i]，以及子树内选取的设备的编号id[i]。

然后我们有如下转移方程：

1. 如果i的子节点j的范围内已经选取了一个设备，那么f[i]+=f[j]+1
2. 如果i的子节点j的范围内没有选取设备，那么我们需要在i的范围内选取一个设备，此时f[i]+=f[j]+1，并且我们需要在i的范围内选取一个设备，那么我们枚举i的所有子节点，选择一个最大的设备进行选择，设其为k，那么我们有f[i]+=f[k]+1,sum[i]+=v[k],id[i]=k。

最后，我们找到f[root]<=s的root节点，输出其子树内选取的设备编号即可。

时间复杂度：O(nlogn)