这天要写的东西其实鸽了……来记今天一个同学问我的一些问题
后续，喜报，现在是 18 早上，17 号直接鸽。
问题 1 ：
给一棵无根 树 \(T = (V, E)\) 。独立询问每个节点 \(v_i\) ，删除 \(T\) 的某个叶子得到 \(T_{1}\) ，继续删除 \(T_{1}\) 的某个叶子得到 \(T_{2}\) ，继续迭代……询问删掉节点 \(i\) 最少需要耗费多少节点？
不妨考虑单独以 \(v_i\) 为根怎么处理。
存在一个显然的 case 1 ，即 \(v_i\) 是一个度数为 \(1\) 的根，则我们可以直接删掉 \(v_i\) ，它在无根树 \(T\) 中也属于叶子。
否则是 case 2，\(v_i\) 的度数 \(> 1\) 。则必然允许删 \(v_i\) 之时，\(v_i\) 剩下 \(\leq 1\) 棵子树，显然易证明 \(v_i\) 剩下 \(1\) 棵子树比剩下 \(0\) 棵子树会严格更优，则不妨令这棵子树为 \(son_{j}\) 。于是有两个显然，一是除了 \(son_{j}\) 外的其他子树必须删完，二是 \(son_{j}\) 内的节点一个都不删最优，于是在选定 \(son_{j}\) 的情况下删掉 \(v_i\) 花费的最少节点为 \(|V| - |son_{j}|\) 。显然答案会随着我们对 \(son_{j}\) 的选择而改变，并且显然 \(son_{j}\) 应当选择 \(v_{i}\) 的最大子树。
将 case 1 代入 case 2 依旧成立。
可以 \(O(|V|)\) DP 出以 \(v_i\) 为全局根，每棵子树 \(x\) 的最大子树 \(mxsz(x)\) 。但为了解决问题，存在 \(|V|\) 次换根，每次换根导致根的最大子树改变。
如果每次重新计算最大子树，则重新贡献 \(O(|V|)\) 的 DP 。考虑换根时 DP ，从当前根 \(u\) 到一个子节点 \(v\) 的换根，\(v\) 的最大子树要么是 \(mxsz(v)\) ，要么是 \(|V| - sz(u)\) 。于是每次换根只需要 \(O(1)\) 时间即可得到新根的最大子树。
时间复杂度依赖于一次 \(O(|V|)\) 的树形 DP 和一次 \(O(|V|)\) 的换根 DP ，总时间复杂度依然为 \(O(|V|)\) 。
问题 2 ：
有同学问背包转移中的状态转移，是否可以先遍历体积再遍历物品。
从组合意义上讲显然可以，从算法优化上讲，因为我们可以只保留体积状态，这意味着一定要一个一个物品做动态规划，那么显然不能将二维空间的遍历顺序转置。
这里我想到了倍增，我们显然知道对于每个遍历系数他的物品状态都提前算出来是对的，证据是他的转移方程 \(f(i, j) \gets f(i - 1, j) + f(i - 1, j + 2^{i - 1})\) 。
显然理论上我们如果能在 j 的物品这意味倒着遍历，则 i 和 j 的顺序也能交换，即 \(f(i, j) \rightarrow f(i + 1, j), f(i + 1, j + 2^{i})\) 。