省选原题翻出来思考一下。
考察第一步如何最优，也就是第一步双方应该如何巴巴博弈。
操作相当于给某个结点的右儿子子树删除，需要使得目前剩下的这棵树叶子结点最小值最大，可以设 \(f_{i, j}\) 为 \(i\) 结点子树内不断操作叶子结点最小值 \(\ge j\) 的最小代价，每次转移要么递归到左右两个子树中解决要么直接将右子树办掉，注意到状态数为所有结点叶子个数和，因此这一步是 \(O(n 2^n)\)。
由于贡献是一个排列，所以最终 Bob 一定会停留在 \(f_{1, i} \le k\) 中最大的 \(i\) 所对应的叶子结点上。思考能否递归求解每一问的问题。
现在 Bob 走到了结点 \(x\)，还剩下 \(m\) 的魔力值可以用，那么同样找到 \(f_{x, i} \le m\) 中最大的 \(i\)，\(i\) 就是下一个对应的叶子，若 \(i\) 在 \(x\) 的右子树中，那么 Alice 必然不会阻止，因为根据 DP，强制让 Bob 走到左子树中反而会使得更优，而 Bob 在和 Alice 巴巴博弈，博弈完之后发现若强行走到左子树会遭到 Alice 的阻止使得答案变劣，此时肯定会走到右儿子，那么走到右儿子后 \(m - f_{ls, j}\)，因为必须要阻止左儿子的一些贡献使得 Bob 不会选择左儿子，然后走回来之后继续递归左儿子，此时 \(m - p\)，\(p\) 是你在右子树的花费，此时不需要减去左子树的贡献是因为在递归过程中会考虑。
如果 \(i\) 在左儿子，那么情况就有点微妙了，此时需要决定：
- 到底选不选 \(w_x\)。
比较假的思路是如果 \(w_x \le f_{rs, j}\) 就选，但是你没有考虑为了让 \(x\) 选完之后右子树还要造成的贡献。
如果选择了 \(w_x\)，需要使得左子树的答案改变，此时才会更优，递归的过程类似于上面。