Description

给出 个点,构造一个生成树,其中某个点如果度数为 会提供 的贡献,求所能构造的最大贡献。

Solution

生成树有 条边,每条边会提供两个度数,于是总的度数一定是 。此外每个点必须满足度数大于等于1,不妨先给每个点先分配度数 ,之后类似于背包做 ,容量为 ,求所能分配的最大值即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48828025