首先发现 \(a_i\) 只会与 \(a_{2\times i}\) 和 \(a_{2\times i+1}\) 两个数交换，所以可以联想到线段树的结构。
考虑按照线段树的方法递归，然后分类讨论。
如果当前递归到 \(i\)，令 \(a\) 表示 \(val_i\)，\(b\) 表示 \(val_{2\times i}\)，\(c\) 表示 \(val_{2\times i+1}\)。
- 如果 \(a<min\{b,c\}\)，那么就不会交换，继续递归 \(2\times i\) 和 \(2\times i+1\) 就可以了。
- 如果 \(b<min\{a,c\}\)，首先肯定要交换 \(a\) 和 \(b\)。可以注意到，交换 \(a\)、\(b\) 的时刻在交换 \(a\)、\(c\) 的时刻之前，所以不可能通过某种交换方式使的交换的效果等同于先交换了 \(a\)、\(b\)，然后交换 \(b\)，\(c\)。也就是说，在 \(b<min\{a,c\}\) 的情况下，只需交换 \(a\)、\(b\) 就已经达到最优了。
- 如果 \(c<min\{a,b\}\)，肯定也是先交换 \(a\)、\(c\)。然后考虑 \(b\)、\(c\) 的顺序是如何。不妨设 \(b<c\)，然后令 \(b\) 放在 \(i\) 的左子树时最终的位置在 \(p_1\)，放在 \(i\) 的右子树时最终的位置在 \(p_2\)。如果 \(p_1<p_2\)，那么 \(c\) 放在左子树时最终的位置 \(p_3\) 一定不小于 \(p_1\)，使得 \(p_1\) 上的数字变大，答案变劣，所以应该将 \(b\) 放在左子树，\(c\) 放在右子树；如果 \(p_1>p_2\)，同理，应该将 \(b\) 放在右子树，\(c\) 放在左子树。现在只需考虑如何求出 \(p_1\) 和 \(p_2\) 就可以了。可以注意到按照这种方式递归的树高只有 \(O(log\space n)\) 的级别，所以深搜加记忆化求 \(p_1\) 和 \(p_2\) 的位置时间复杂度就是对的了。