解题思路

把最终铺设的所有灯带看成一些被选中的点和边。

由于原图是一棵树，因此选出的边不可能形成环。只要保证每个被选中的点连接的被选边数量不超过 $2$ ，那么每个连通块就一定是一条路径，恰好对应一条灯带。

设一共选择了 $V$ 个点、 $E$ 条边、形成 $K$ 条路径。因为选出的图是森林，所以有

$K=V-E$

题目内容

古镇准备办灯会。巷道连通 $n$ 个灯位，灯位编号 $1\sim n$ 。巷道没有环，任意两个灯位之间恰好有一条路可走，也就是说这 $n$ 个灯位和 $n-1$ 条巷道构成一棵树。

第 $i$ 个灯位挂灯后的预计人气收益为 $v_i$ ，可以为负

灯带必须沿着树上一连串巷道铺设，也就是树上的一条路径（可以只覆盖一个灯位）。每启动一条灯带，都要在路径的一端接入一个电箱，花费启动费 $C$ 。一条灯带的净收益为「它覆盖的灯位收益之和」减去 $C$ 。

$1.$ 电路容量有限，同一个灯位最多只能属于一条灯带，两条灯带不能共用任何一个灯位。

选择提交后点击「开始AI分析」