一类将度数变为 1/2 的优化建图 笔记

有以下特点：儿子数和复杂度强相关，不同子树的本质相同，按照一定的顺序做 / 判定，答案不变。

1. P6326 Shopping

不知道为啥很快就会了只有一个儿子的情况（实则对树形背包不熟练导致的），就是强制选一个自己的物品，直接合并儿子的背包，再对自己剩下的物品做多重背包。

但是有多个儿子就会面临背包合并的问题，时间复杂度来到 $O(n{m}^2)$，但事实上可以建一个每个点只有一个儿子的图，考虑每个点的 dfs 序向 $\mathrm{dfn}+1$ 连边，不选就是直接把原树自己整棵子树外的背包当成自己的背包，选就是自己和儿子的背包做上述合并，这样就是 $O(nm)$ 的了。

2. P3665 [USACO17OPEN] Switch Grass P

首先，答案一定是一条边；其次，答案一定是 MST 上的一条边。

使用 multiset，$O(n\log n\times \mathrm{deg})$ 的是容易的。

考虑 Kruskal 重构树，相当于要找深度最大的虚点，满足左侧子树的阵营都相同，右侧子树的阵营都相同，左右侧子树的阵营不同。

此时就发现左右本质都一样了，究竟是左边哪个点连向右边哪个点已经不重要了，于是直接把左子树看作一条链，右子树看作一条链，合并就用这条边把两条链合并成一条链，于是这样 $\mathrm{deg}\le 2$，可以通过。