题目内容

某通信公司计划对网络中的所有基站进行升级维护。网络由 $n$ 个基站和 $n-1$ 条双向链路组成，基站编号为 $1$ 到 $n$，保证任意两个基站之间可以通过链路互相到达。

公司预留了充足的资源，但必须在升级过程中使用完，否则多余的资源会被回收。升级可以采用两种方式：

• 方式一：选择一个尚未被升级的基站，消耗 $x$ 单位资源，废弃该基站以及其所有直接相连的链路（这些基站与链路不再存在于网络中）。
• 方式二：选择一个尚未被升级的基站，消耗 $y$ 单位资源，升级该基站所在的由尚未升级的基站和尚未废弃的链路构成的整个连通块，连通块内的所有基站和链路均被废弃。

每种方式可以反复使用，直至所有基站和链路都被废弃。公司希望尽可能多地消耗资源，请你计算最大可能消耗的资源总量。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写