Description

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

Solution

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

Code

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