NOIP2022模拟赛二 By YJC 10.20
A P1330 封锁阳光大学
每个连通块单独考虑，分别黑白染色，取黑白中数量较小即可。
90701973
B CF436E Cardboard Box
对于每个关卡，分成两类：
- 2a_ileq b_i：将选两个点拆成 a_i 与 b_i-a_i，有 a_i < b_i - a_i
- 2a_i > b_ib_i 排序，此时一定先选两个更优。
一类点直接拆散按从小到大排序选即可。
考虑枚举选一类点 i 个，则剩余 m-i 个点填二类点分 m-i 的奇偶性判断：
- m-i 为偶数：恰好选前 (m-i)/2 个两个即可。
- m-i 为奇数：选 (m-i-1)/2 个两个，再加上一个一个；或选 (m-i 1)/2 个两个，再将其中一个两个转为一个。
显然奇数情况记前/后缀最小/大值即可。
C AcWing 359. 创世纪
在一内向基环树森林上选若干点，使每个点必有一个儿子没选，求权值和最大。
表示当前点选/不选的最大值。
考虑非树边 xrightarrow y，有两种情况：
- 不选 y，则 x 无限制。
- 选 y，对 x 无影响，可直接将 xrightarrow y 断开。
两者取最大即可。
D P2664 树上游戏
对于每个点，每种颜色，其单独答案贡献可转化为 n-siz_{x,c}。
其中 siz_{x,c} 代表从点 x 出发，不经过颜色 c 的点，所构成的连通块大小。
考虑对于所有 siz，均挂在深度最小的节点上，之后树上差分统计即可。
若碰到与当前颜色相同的点，之后该子树将失效，贡献更新。
注意根节点父亲颜色应设为“全彩”，特殊考虑即可。
