QOJ 14601
洛谷 P14280
看起来没什么思路，不妨推推样例，从局部入手。
对于一个以 \(u\) 为根的子树，插入方式就是：插入一个到左子树 、交换左右儿子、插入到左子树……
设插入到的子树是 \(u\) 最终的左儿子（L）/右儿子（R），则这个子树的插入序列一定是 uLRLR...L(1) / uRLRL...L(2)，看起来插入方式是比较固定的。
但还有一种情况，就是最开始有一个子树，然后插入 \(u\) 后成为 \(u\) 的左子树。于是又多了两种方式：LLL...LuRLRL...L(3) / RRR...RuLRLR...L(4)，最开头的连续的 L/R 个数可以由左右儿子子树的大小确定。
于是这个题的思路就出来了，对于 \(u\) 的子树，先求出左右儿子对应的最小和最大字典序。然后枚举 \(4\) 种情况求解。
设 \(d = 左子树大小 - 右子树大小\) 。
- 若 \(d \ge 2\)，只可能是情况 \(3\)。
- 若 \(d \le -1\)，只可能是情况 \(4\)。
- 若 \(d = 0\)，最小字典序对应情况 \(2\)，最大字典序对应 \(4\)（最开头只有 \(1\) 个
R，相当于u, R交换一下）。 - 若 \(d = 1\)，最小字典序对应情况 \(1\)，最大对应情况 \(3\)。
具体操作方面，碰到一个 L 就取出左子树序列的第一个，R 取出右子树序列的第一个即可。
直接做是 \(O(n^2)\)，但是我们只需要让子树 \(u\) 的代价之和轻儿子有关就是 \(O(n \log n)\) 的，所以直接把连续的 L/R 继承下来即可。
这个题看起来没什么思路，可以尝试从局部入手，分析可能的插入情况，多推推样例。