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