H. Sweet Sugar
一个经典贪心是从下到上，如果子树 \(u\) 剩下的部分（一定包含 \(u\)）包含合法连通块，那么这个连通块给答案贡献 \(1\)，切断 \(u\) 与 \(fa[u]\) 的边
key observation：如果一个连通块权值和为 \(x\)，那么一定可以通过删叶子得到权值和为 \(x-2\) 的连通块
所以只需要 dp 权值和为奇/偶数的最大权值和即可。注意权值和为奇数的初值和转移需要特判
2023 CCPC 桂林题解
发布时间 2024-01-09 22:49:51作者: ft61