首先肯定有这么一个数，每次操作要么是把它和它左边的合并，要么把它和它右边合并。所以枚举这个数，然后它向两边 ，然后发现，它前缀 和后缀 都是只有 段，肯定每次是向左到段首或者段尾，这就 了；实际上，设 表示 出发的 个段，这一段的最小代价，同理设 ，这样就能把复杂度压到 。
首先，一个 DAG 可以做到任一点距离小等于 ；那么我们要把图划分成一个 DAG 和一个可以被 DAG 一步到达的点集，增量构造即可。
有几个切面可以思考：
第一个事情告诉我们，把豌豆按照中点排序，那么可以按顺序 dp。事实上，可以 wqs 套 dp。
第二个事情给了我们求 的方式，而我们要求出所有 ，这东西的决策点也满足决策单调性。
首先：若 且 ，那么这个位置 就相当优秀，两个人都会去避免 ，最后先手顶不住了，不得不取了 ，那么后手取了 ，先手取了 ；那么这就相当于一个价值 的石子。
于是所有序列只有单谷的情况了，可以直接把所有石子从大到小排序，两个人轮流选。
首先考虑逆序对数为 的排列数怎么求：相当于求一个物品为 的多重 01 背包的方案数。
树的深度也非常难限制，所以将其用期望的线性性进行转化：对每个 ，求出 作为 祖先的方案数。然后发现我们先确定 ，再确定 ，再确定别的数，这就相当于把背包去掉了 这个元素，仅此而已，于是做完了。
法一：所有连通块大小的和为 ，这不禁让人想到自然根号，对于大于 的连通块，它至多有 个；对于小于 的连通块，它的代价为 ，而 。
法二：考虑 ，枚举了 后，剩下两个 是独立的，那么可以点分治，然后先后枚举两个儿子，分别往背包里加即可。。
法三：法二的枚举 是很废的事情，考虑 up and down 维护这件事情，设 表示 点上和为 的方案数，向上转移一遍，再向下转移一遍，最后容斥掉 下方两个点相同的情况即可。。
首先有一个区间 dp：设 表示答案，利用决策单调性可以优化到 。
注意到对于 ，一定有 。所以考虑固定 ，考虑 作为分段常数函数它是怎么分段的。
首先 ；然后设 是最大的位置使得 ，假设已经知道了 ，怎么求出 ？有转移式：
但是，由于有 ，所以发现用 来转移是不优的，所以有：
直接用记忆化或者主席树来优化转移，会发现总状态数已经正确了，只是时间效率还是略低，会导致被卡常，获得 分。以下为题解所述的进一步思路：
称 为极大区间，当且仅当不存在 使得 ，也即 且 。我们有：极大区间的量级是 的。证明：
设 表示长度为 的区间的极大区间数量的最大值，设全局最大值位于 位置，那么：
表示长度为 的序列，最大化跨过 的极大区间数量。设 的极大区间 的数量为 ，那么有：
求和可得：，根据归纳法： 证毕。
如上复杂度分析启发我们一个做法：维护区间集合 表示所以极大的区间使得 （注意，和极大区间的定义不同哦），那么考虑 ，它会将一些区间“合并”，再插入所有 的位置，那么可以用双向链表维护，再用一个数组维护这次会发生变化的位置集合，注意到每次修改产生的新区间，一定是 的极大区间，只要避免访问不需要变化的区间就可以做到总复杂度正确。
感觉 OI 在这方面的量级分析上不是很有直观。
根号做法：对操作序列分块，对每一块分别预处理树上的每个点它经过了这个块会到达哪里，预处理方式：建出这 个点构成的虚树，对于虚树上的每一条边（也就是原树上的链），维护一个双端队列，队列的每个元素是当前在这个点上面的点集构成的链表；对于每一次操作，都只会进行 次链表和队列的修改操作；而虚树外的点，都只会被在某个特定的时刻加入虚树。
双 做法：刚刚做法没有用上离线！在 时间把点插进去， 时间再查查点跑到哪里了。树剖，剖完了每条重链上维护它上面的每个点，它上面的点集。除了当前操作的那个点位于的那 个重链之外，其它的点都是向上移动，它最多会跳 次重链，只在它位于的重链发生变化时，提取出变化的那个点集对应的并查集向上归并，总的势能只有 ；而当前重链上的点，可以一起向下移动，新产生的势能也只有 。
考虑维护一个当前的连通块，并且已知左部点为 ，右部点为 ，考虑怎么扩大这两个集合。
除了这个已知的连通块之外，假如我们还知道这张图的一些边，这些边把图分成了若干个连通块 ，维护循环指针 分别指向 中的一个点。
不断进行如下操作，询问 点集内是否有边：
无效操作什么都进行不了，这种情况下的势能证明如下：假如经历了若干次无效操作后，进行了二操作，那么 的增量大等于此前无效操作数量，那么势能正确了；假如进行的是一操作，可以看作是不会影响别的 的势能，只是会影响 和 两个集合的势能，可以把新指针指向其中较大的集合的原有指针，那么势能多花费的至多只有小集合的大小，符合启发式合并的分析，总的势能增量是 。
来自 Michael 的更为精确的证明：势能分析就是在说这样一件事：设 中点数分别为 ，则在 次操作内，要么有连通块和当前连通块合并，要么有两个连通块合并（不对，不一定会有）。
应该这么表述，一个连通块 ，随着 和 的增大，它在某一时刻存在了一条连向 的边，从这一时刻起，它至多经过 次无效操作就会被合并进 里；记势能为，所有已经有边连向 的 集合中，它的 还需要 几次， 才会指向那个能连到 的点。势能增加有两种情况：第一种是，随着 增大， 开始和 直接相连了，对势能增量为 ；第二种是合并了两个集合 ，那么把 指向其中大的那个的 ，不妨设 ，若 直连 ，那么势能最多上升 （也即 ，符合启发式合并的复杂度分析），否则若 直连 ，则势能最多上升 ，而这种情况，每个叶子只会贡献到 里至多一次；其余情况，势能一定会下降。