H. Sweet Sugar
一个经典贪心是从下到上,如果子树 \(u\) 剩下的部分(一定包含 \(u\))包含合法连通块,那么这个连通块给答案贡献 \(1\),切断 \(u\) 与 \(fa[u]\) 的边
key observation:如果一个连通块权值和为 \(x\),那么一定可以通过删叶子得到权值和为 \(x-2\) 的连通块
所以只需要 dp 权值和为奇/偶数的最大权值和即可。注意权值和为奇数的初值和转移需要特判
一个经典贪心是从下到上,如果子树 \(u\) 剩下的部分(一定包含 \(u\))包含合法连通块,那么这个连通块给答案贡献 \(1\),切断 \(u\) 与 \(fa[u]\) 的边
key observation:如果一个连通块权值和为 \(x\),那么一定可以通过删叶子得到权值和为 \(x-2\) 的连通块
所以只需要 dp 权值和为奇/偶数的最大权值和即可。注意权值和为奇数的初值和转移需要特判