P8677 [蓝桥杯 2018 国 A] 采油

LQ 公司是世界著名的石油公司，为世界供应优质石油。 最近，LQ 公司又在森林里发现了一大片区域的油田，可以在这个油田中开采 $n$ 个油井。 LQ 公司在这 $n$ 个油井之间修建了 $n-1$ 条道路，每条道路连接两个油井，路径中间不会路过任何油井，而且这些道路将所有油井连通。 建立油井的时候需要使用一台大型设备，运输起来非常麻烦，LQ 公司准备在其中的一个油井位置建立一个空运站，先将设备空运到空运站，之后每次经过他们建立的道路来运输这个大型设备以建立不同的油井，当油井建立完毕后再从空运站将大型设备运走。 为了减少运输的麻烦，公司要求大型设备在道路上运输的总路程是最短的。 在建立油井和采油的过程中需要花费一些人力，第 $i$ 个油井需要花费 $B_i$ 个人，而一旦油井建成，就需要 $S_i$ 个人一直坚守在油井上进行维护。 当然，如果一个人参与了油井的建设，他可以直接留下来维护油井，或者参与下一个油井的建设，但是在维护油井的人不能再参加后续油井的建设了。 现在 LQ 公司想知道，大型设备运输的总路径长度最短是多少？在保证总路径长度最短的情况下，LQ 公司至少需要花费多少人力才能完成所有油井的建立与维护。

无

无

**【样例解释】** 有两种方案达到最优。 方案一：在油井 $2$ 建立空运站，先建立油井 $2$，再将大型设备运输到油井 $1$ 建立油井 $1$，最后将大型设备运回油井 $2$。 方案二：在油井 $1$ 建立空运站，先将大型设备运输到油井 $2$ 建立油井 $2$，再将大型设备运送到油井 $1$ 建立油井 $1$。 **【数据范围】** 对于 $20\%$ 的数据：$n$ 不超过 $10$； 另外 $20\%$ 的数据：每个油井最多和两个油井之间有道路直接连接； 另外 $10\%$ 的数据：有 $n-1$ 个油井只有一条道路与其他油井连接； 对于 $100\%$ 的数据：$1\le n\le10^5$，$B$、$S$、$c$ 均为不超过 $10000$ 的正整数。 时限 1 秒, 256M。蓝桥杯 2018 年第九届国赛