说一下自己赛时做法。赛时会了，但没能调出来，几乎确定进不去队了，留下这篇题解作为这次比赛的记录吧。
称激活守卫为打开开关。
首先考虑，如果确定所有开关的情况，Bob 有一个简单的贪心做法：当走到一个点时，递归其左右子树并得到两个序列，若右子树的对应序列的小于左子树的对应序列，则右边更优，若开关未被打开，他就会往右走；否则往左走。
考虑能否记录一些简单的东西供 A 参考。
首先，记录剩余魔力值一定是不可能的，这启发我们记录某个决策需要花费的最小魔力值，若剩余魔力值大于它，则该决策可行。
那么我们需要比较两棵子树构成的序列，并据此给出代价。
注意到叶节点上是排列，因此只需记录序列的第一位即可比较大小。因此有自然的想法：在节点 \(u\) 上记录很多 \((v, d)\)，表示：站在 \(u\) 上遍历其子树，若 \(< q_v\) 的所有节点都不可达，且 \(q_v\) 可达，需要花费的最小代价。
求出 \((v, d)\) 后，每次贪心选择让 \(v\) 最大的方案并往下走。假设 \(v\) 在左子树，那么，先把魔力值全部供左子树使用，再将多余的魔力值给右子树使用。为了保证左右子树独立，我们可以再添加一个数 \(t\)，表示，为了让 \(u\) 处 \(< q_v\) 的节点不可达，异于 \(v\) 一侧需要花费的最小代价。容易发现扣除 \(t\) 后向下递归，将多余的魔力值与 \(t\) 一起传进另一侧的子树，最优，且一定合法。
显然，魔力值越大，就可以让一棵子树的字典序越大，这里允许不用完的情况。
最优性：首先此时 \(v\) 最大。因为异于 \(v\) 一侧花费的魔力值最小，\(v\) 所在子树能获得最多的魔力值，即字典序一定最大。
合法性：另一侧的子树可达的权值最小点一定大于 \(q_v\)，字典序增大后仍然成立。
所有 \((v, d, t)\) 加起来不超过 \(n 2^n\) 个，如果我们可以在获得 \(u\) 的左右儿子的 \((v, d, t)\) 的情况下，\(O(siz)\) 求出 \(u\) 的所有 \((v, d, t)\)，则问题被解决。
考虑按 \(v\) 做归并排序。
假设当前左侧扫到 \((v_l, d_l, t_l)\)，右侧扫到 \((v_r, d_r, t_r)\)。设左侧小于右侧，则 \(d=\min\{w_u, d_r\}\)；否则 \(d=d_l\)，当 \(l, r\) 不存在时视为正无穷。\(t\) 可以简单讨论得出，需要同时记录是否开启 \(w_u\)。我实现时 \(t=-1\) 代表开启 \(w_u\)，因为显然此时不需要为右边预留魔力值。
综上，这道题做完了。
等我调完了放代码。
标签：子树,魔力,记录,省选,题解,节点,序列,联考 From： https://www.cnblogs.com/purplevine/p/18051617