搬题人：
验题人：
原题：
你可以在原题中找到非中文的题解，中文题解会稍后发布。
这是我第一次给 pjudge 搬题，不足知处请多多包涵。
你可以在本帖中尽情开喷，我会在下一场 pnr 中改进。
令操作结束后序列是 y1,y2,⋯,yn，容易发现，把 x,y 分别排序，将 x1 变为 y1，将 x2 变为 y2 ……，是最优的。
于是问题变成了，把 xi 升序排列后，要求对于所有 i(2≤i≤n),xi−xi−1≥d，求最少操作次数。
考虑其差分序列，直接套用 UOJ-雪灾与外卖 的模拟费用流算法，能得 70 分。
再次转化，将 xi 减去 (i−1)d，问题就变成了让 xi 不降，求最少操作次数，这个能直接做到 O(nlogn)。
先拆一下贡献，对于每条边，将它的经过次数加到答案里，最后答案加上 2(n−1)，就是真正的答案。
考虑把 u 挂在 v 上的过程，令 S 表示 u 所在连通块的点集，则 find(u) 到 find(v) 这条边的经过次数为：−2(|S|−1)−1+∑x∈Sdeg(x)。令这一坨式子为一个连通块的权值，显然，我们应该把 u,v 所在连通块中，权值较大的挂在权值较小的上面。
继续观察，假设 u 所在连通块的权值比 v 大，那么把 v 里面的点一个一个挂到 u 上一定是更优的。
枚举起点，将树定根在起点，问题变成了，每个点有一个权值，将 0,1,⋯,n−1 放到每个点上，要求父亲的数大于儿子，最大化每个点上权值乘上数的和。这是经典的问题，每次取权值最大的，它上面的数一定是父亲的 −1，将它和父亲合并就行，新权值设为连通块内的平均数。
复杂度 O(n2logn)。
考虑最朴素的 dp：dp(i) 表示前 i 个数的最大价值，转移 dp(i)+mex(i+1,j)⋅sum(i+1,j)→dp(j)(j−i≤k)。
从 1 到 n 依次计算 dp 值，令当前算到的位置为 i，先维护每个位置到 i 这一段的 mex，直接开珂朵莉树维护其连续段，能分析出总共只有 O(n) 次连续段的变化。
转移考虑根号重构，令 B=⌊√n⌋，若 imod，则重构 [i-k+B,i] 这一段的贡献，转移的时候对于散块暴力算，复杂度 O(n \sqrt {n})，实现起来很多细节。
据说存在 polylog 做法，敬请期待官方题解（。
考虑 dp，dp(i) 表示，考虑前 i 个数，a_i 选了，的最大权值，转移枚举 j(j \gt i)。
优化转移，如果 i,j 之间有一个 k(i \lt k \lt j)，且 a_i \&a_k 的最高位和 a_i \& a_j 相同，那么选上 a_k 一定更优（2 \cdot 2^{a_i \& a_j 的最高位} \gt a_i \& a_j，枚举 a_i \& a_j 的最高位，找到前面第一个这一位是 1 的数转移就行，复杂度 O(n \log A)。
赛时有人挂，原因是没考虑 a_i \& a_j=0 的情况，hack：a=\{4,4,2,2\}。
fun fact: pb 认为这个题是一眼题。
最直观的一个结论：除了最后一条命，都只做”深入思考“操作。
考虑二分，二分复活次数 d，计算经过 d 条命的“深入思考”后，最少在下一条命中需要多少时间能完成任务。最后一条命，每个任务需要的时间是：
考虑这样一个贪心策略，每次选择能减少时间最多的进行“深入思考”，原因是代价关于 t 是凸的。
假设任务 i 被想了 t 次，则需要满足：t \le d, \sum t \le c \cdot d。
但是 c,d 可能会特别大，观察到对于 t \ge 2d 的任务，进行一次“深入思考”会产生 d 的时间减少。将所有任务按 d 从大到小排序，尽可能操作直到 t \lt 2d 或操作次数用完。之后每个任务至多被操作两次，把这两次的时间减少量搞出来再贪一遍就行。
复杂度 O(n \log n \log A)。
fun fact: 我认为这个题是一眼题。
考虑点双缩树，x 走到 z 必须经过 y，当且仅当 y 是割点，且 x 和 z 在 y 的不同子树中。
分 y 是否在 x 子树两种情况讨论，每种情况都分别令 O(1) 个 dfs 序区间内的点不合法。
复杂度 O(n \log n)，有一种情况需要求 x 的 dep_y-dep_x-1 级祖先，
fun fact：这个题成为了签到题，前三题通过 18,12,22 位选手。
讲下我的做法，实测 118 次操作，能过原题。
考虑只有 0,1，将连续段放在一起考虑，序列形如 10101010 \cdots，考虑一次操作让 0 连续段个数减半，分段类似 1|0|10|1|0|10\cdots，最后可能会搞出 101 的形式，再来一次操作 1|01，就能排好序了。
考虑分治，将 \le n/2 的看成 0，\gt n/2 的看成 1，进行只有 0,1 的算法，然后往两边递归，同一层可以放在一起处理，如果最后顺序不对再整体 reverse 一下就行。操作次数大概是 0.5 \cdot\log^2 n
先考虑循环节，等概率选取一个长度为 n 循环节为 d 的字符串，考察最小表示在 f 处的概率，若 f \le d，则概率为 d^{-1}，否则为 0。
先计算循环节为 d 的字符串个数 cnt(d)，这个可以用莫反求，cnt(d)=\sum_{c|d} \mu(c)26^{d/c}。
然后问题就变成了，每次询问两个数 m,n，求等概率选择一个长度为 n 的字符串和一个长度为 m 的字符串，最小表示位置相同的概率。枚举位置 f，概率是 (\sum_{d|n, f \le d}cnt(d)d^{-1}26^{-n}) \cdot (\sum_{d|m, f \le d}cnt(d)d^{-1}26^{-m})。
观察到两部分都可以被分为至多 \sqrt{A} 段相等的连续段，A 是值域，复杂度 O(n \sqrt{A})。
部分分在暗示做法。
最关键的一个性质：考虑第 i 个数 h_i 在最后被换到了 p_i 的位置，那么最终状态下，第 p_i 个数是 (-1)^{i-p_i}h_i，且操作次数是 p_i 的逆序对数。
先考虑 |h_i| \neq |h_j| 的部分分，按绝对值从大往小枚举，当前枚举到的数，要么丢到末尾且符号为正，要么丢到开头且符号为负。令 dp(i,0/1) 表示，已经枚举了前 i 个数，开头的数模 2 是什么。转移只需要用 BIT 优化一下计算逆序对。
再考虑 |h_i| \le 1，由于符号翻转很烦，需要一点点的转化去掉它。令初始状态为 a_1,\cdots,a_n，目标状态为 b_1,\cdots,b_n，对于所有奇数（偶数也行）的 i，将 a_i,b_i 取相反数，操作就变成了“交换相邻数，没有符号翻转”（理由：转化前后对于符号的要求均为，若 |i-p_i| 为偶数，需要 a_i,b_{p_i} 符号相同；若 |i-p_i| 为奇数，需要 a_i,b_{p_i} 符号相反）。
在转化后的问题上，需要对于一个 -1,0,1 的序列求出，变成某个序列（中间一段为 0，左右两段 +1,-1 交替排列）所需要的最小交换次数。
先做单组询问：给最终状态用 [1,n] 顺次标号，给初始状态中的标号满足：对于所有 x,y，第 x 个数 y 在两个状态中的标号相同。操作次数就是初始状态标号的逆序对。
对于多组询问需要一点分讨，一个稍微简单的做法是，分 0 左边的数有奇数还是偶数两种情况。对于同种情况，将 0 的区间往右移动两步后，标号序列的变化也仅仅是将两个数的标号移到中间一段 0 的前面，很容易用 BIT 计算逆序对的变化量。
考虑满分做法：dp 状态一样，按绝对值 x 从大到小枚举的时候，将 +x 看成 +1，-x 看成 -1，绝对值小于 x 的看成 0。有时候 0 会很多，但是计算逆序对的时候只需要分别计算：(-1,0),(1,0),(-1,1) 之间的贡献，额外用 BIT 维护 0 的位置即可。
复杂度 O(n \log n)。
不会，咕
不能掉到 0 以下，这个限制特别烦。如果某一天掉到 0 以下，那么这一天之前所做的练习都是无效的。也就是说一定存在一个最优方案，在开始练习一个技能之后，一定不会掉到 0 以下。
令 dp(i,0/1/2,d_1,d_2) 表示，考虑前 i 天，第 i 天练习了什么技能，另外两个技能分别有多少天没有练习。一个非常直观的感觉，d_1,d_2 不会太大，是 O(\sqrt {A}) 级别的，A 是值域。感性理解就是，超出这个级别会导致掉下来太多，而在这一段没有练习的时间的正中间强制练习这个技能，会取得 \ge A 的收益，复杂度 O(nA)，注意一下要处理一些技能没开始练习的情况。
将图看做 100 个点的完全图，每条边染成了黑色或白色。
先取出任意五个节点，解出这个大小为 5 的团。每三个询问一下，得到了 10 个未知数和 10 个方程，把它解出来。由于未知数不多，可以暴力枚举。
每次选一个点 u 加入团，将团中的节点随机打乱，得到排列 p_1,p_2,\cdots,p_k，令 i=1，询问 (u,p_i,p_{i+1})，将其减去边 (p_i,p_{i+1}) 的贡献，有两种情况。
有一些细节：如果找完了都没有找到同色边，那么可以任意取一个 j，询问 (u,p_j,p_{j+2}) 或 (u,p_1,p_j)，得到 (u,p_j) 和 (u,p_{j+2}) 的颜色，由于 k \ge 5，一定能找到一个合适的询问。
我们已经将团里面的点随机打乱了，每次问到同色的概率至少是 0.5。即，一次询问在最坏情况下，有 0.5 的概率确定两条边，有 0.5 的概率确定一条边，期望确定 1.5 条边，询问次数期望大约为 \frac{n^2}{2 \times 1.5}=\frac{n^2}{3}。
考虑 2-sat，有 2n 个 0/1 变量 x_0,x_1,\cdots,x_{2n-1}，每个变量表示 x 轴上的一个点所在连线的方向，是向上还是向下的。想到这个，剩下的通过手玩都可以解决。
令 l_i,r_i 表示颜色 i 靠左，靠右的两个点的位置。
手玩 2^4 种情况会发现是必要且充分的，构造方案可以对每个 l_i 上的竖线钦定长度，l_i 越小越长。用 2-sat 或并查集求解，复杂度 O(n^2)。可以主席树优化建图，复杂度 O(n \log n)。
又是大缝合怪！但每种情况想起来都蛮有意思的。
咕
假设我们钦定要组成 x 个等腰三角形，可以贪心的凑出最大的 x 对腰。检查是否合法是一个二分图匹配状物，考虑 Hall 定理，令 a_x 表示长度 \le x 的腰选了几对，b_x 表示长度为 x 的腰总共能选出多少个合法的底，则对于所有 x 有 a_x \le b_x。
二分 x 特别不好做，查询 a_x,b_x 很麻烦，我们有更好的解法。
考虑这样一个过程：先不管是否合法，配出最多的腰，然后拆散一些腰作为底使其合法。
用支持区间加，全局 max 的线段树维护 a_x-b_x，查询时找到最大值，拆散一对腰会使得最大的 a_x-b_x 减去 3（a_x 减去 1，b_x 加上 2），复杂度 O((n+q) \log n)。
对于所有 M 种物品各建立一个点，所有 N 段区间各建立一个点。考虑连出一个二分图：物品连向区间表示这个区间需要一个这种物品，区间连向物品表示这个区间多出一个这种物品（如果多出多个就连多条边），更形象的说，就是用边去刻画物品的流向。
显然每个点的入度等于出度，每一个联通分量都有欧拉回路，找出后构造是容易的。
复杂度 O(NM)。
令 L,M,R 表示 left_num, my_num, right_num。
先忽略下午和晚上，我们需要找到一个函数 f(x,y)，满足对于任意 x,y,z(x \neq y,y \neq z)，有 f(x,y) \neq f(y,z)，每个人在上午只需要返回 f(M,R)。
考虑 x,y 的二进制表示，找到任意一位 x,y 不同的二进制位，令其为第 d 位，x 在这一位上的数是 b，令 f(x,y)=2d+b，如果 f(x,y)=f(y,z)，则 x 的第 d 位和 y 的第 d 位是相同的，与定义矛盾。
f(x,y) 的值域是 [0,2 \lceil\log A\rceil)，其中 A 是 x,y 的值域。
上午下午晚上都返回 f(M,R)，值域是 10^5 \rightarrow 34 \rightarrow 12 \rightarrow 8。
但是我们没有用 L，如果在下午晚上返回 f(f(L,M),f(M,R))，值域是 10^5 \rightarrow 34 \rightarrow 12 \rightarrow 8 \rightarrow 6 \rightarrow 6。
这个方法有一个明显的弊端，因为 2 \lceil \log 6 \rceil = 6，有再多次的操作也无法缩小值域。
一个特别天才的想法：将每个数映射到一个 01 个数相等的串，虽然会扩大串长，但是由于一定能找到一个不同的二进制位满足 x 在这一位为 0，故 f(x,y) 只需要返回 d，可以突破 6。
早上，值域是 10^5，\binom{20}{10}=184,756，可以映射到 20 位。
下午，计算 f(L,M),f(M,R) 的时候，值域是 20，\binom{6}{3}=20，可以映射到 6 位。
下午，计算返回值的时候，值域是 6，\binom{4}{2}=6，可以映射到 4 位。
晚上的想法比较简单，如果 M \le 2 直接返回 M，否则返回一个不是 L 也不是 R 的数，这个数一定可以在 0,1,2 中找到，得到满分做法。
没有奇环，说明是二分图。
删掉最少的权值的边，变成二分图，可以看成在保持是二分图的情况下保留尽可能多的权值。
考虑 dp，dp(i,0/1,0/1,0/1) 表示，考虑子树 i，i 填了什么颜色，i 子树内最左边和左右边的叶子填了什么颜色。合并 u 的所有儿子的时候，令 f(j,0/1,0/1,0/1) 表示，目前合并了 j 棵子树，我们即将要在 u 上填什么颜色，目前合并的子树中，最左边和最右边的叶子填了什么颜色。
复杂度 O(n)。
假设我们已经确定了要拍哪些区间和对应的力度，按照力度降序排列，令它的影响范围为目前没有被拍的所有位置，由于所有区间长度相等，这个范围也是一个区间。
将整个序列的所有影响区间抠出来，容易发现一个影响区间所需要的力度是区间内的最大值，也就是说问题转化成：将序列 S 划分成若干连续段，每一段的长度 \le K，最小化每一段最大值之和。
令 dp(i) 表示前缀 [1,i] 的答案，转移 dp(i)=\min_{j \in [i-K,i-1]} dp(j)+\max\{S_{j+1},\cdots,S_i\}。
再观察这个式子，发现只需要考虑 i-K 的决策和 S_j 是 [j,i] 中的最大值的 j 的决策（理由：dp(i) 显然不降，在保证 \max 不变的时候，选取更小的 j 不劣）。把这些 j 拿出来，令其为 a_1,a_2,\cdots ,a_m，则 dp(i)=\min_{i \lt m} dp(a_i)+S_{a_{i+1}}。
i-K 的转移可以用滑动窗口维护；a 的变化仅有：右边 push/pop，左边 pop，可以用双栈维护，复杂度 O(n)。
写了大半天的随机化，卡在了 Test #52，为什么过不去后面再说。
将所有数按模 4 意义分组，令 S_0,S_1,S_2,S_3 表示四个集合。
考虑全是偶数的情况，此时一定有解，因为两个 S_0 中的元素，或两个 S_2 中的元素，对其操作之后一定产生一个偶数，不断这样操作，不能操作的时候要么已经操作完，要么 |S_0|=|S_2|=1，此时将剩余两个数操作即可。全是奇数同理。
对于一般情况，先要证明一个引理：
证明：以 |S_0|,|S_2| \ge 1 为例，保留两个集合各一个元素 x_0,x_2，将剩下的奇数和剩下的偶数随便操作，可能会得到：
如果我们能构造出一个 S_0 中的元素和一个 S_2 中的元素，或者构造出一个 S_1 中的元素和一个 S_3 中的元素，随便操作后暴力解剩下的四个数，问题得以解决。
以 S_0 和 S_2 为例，找出所有偶数中最低的二进制位 d ，满足所有数在这一位上不全部相同。任意找出两个不相同的数，不妨设两个数为：a_12^{d+1}+b 和 a_22^{d+1}+2^d+b，操作这两个数，得到 (a_1+a_2)2^d+2^{d-1}+b，此时第 d-1 位一定改变，将 d 减去 1 继续进行同样的过程，注意先判断数够不够。
复杂度 O(n \log A)，A 是值域。
随机化过不去的原因：在 Test #52 中，d 比较大，严格限定了其中很多步操作。
将图看做 100 个点的完全图，每条边染成了黑色或白色。
先取出任意五个节点，解出这个大小为 5 的团。每三个询问一下，得到了 10 个未知数和 10 个方程，把它解出来。由于未知数不多，可以暴力枚举。
每次选一个点 u 加入团，将团中的节点随机打乱，得到排列 p_1,p_2,\cdots,p_k，令 i=1，询问 (u,p_i,p_{i+1})，将其减去边 (p_i,p_{i+1}) 的贡献，有两种情况。
有一些细节：如果找完了都没有找到同色边，那么可以任意取一个 j，询问 (u,p_j,p_{j+2}) 或 (u,p_1,p_j)，得到 (u,p_j) 和 (u,p_{j+2}) 的颜色，由于 k \ge 5，一定能找到一个合适的询问。
我们已经将团里面的点随机打乱了，每次问到同色的概率至少是 0.5。即，一次询问在最坏情况下，有 0.5 的概率确定两条边，有 0.5 的概率确定一条边，期望确定 1.5 条边，询问次数期望大约为 \frac{n^2}{2 \times 1.5}=\frac{n^2}{3}。
令 dp(u) 表示从节点 u 出发，最少需要多少的起始资金才能无限行走下去。转移 dp(u)=\min_{(u,v,r,p) \in G}\{\max\{r,dp(v)-p\}\}。
图中有环，不好处理。先考虑不断将所有出度为 0 的点删掉，这个可以在反图上用拓扑排序解决。然后我们得到的图满足，只要有足够的钱，在任意节点都可以无限走下去。找出 r 最大的一条边 (u,v,r,p)，用 r 去更新 dp(u)，并把这条边删去。此时可能会出现出度为 0 的点，继续在反图上拓扑排序更新 dp。
复杂度除排序外 O(n+m)。
称一个数在山谷里，当且仅当在左边和右边都有严格比它大的数。
观察这样一个过程，将所有在山谷里的数的最小值整体 +1。
每次操作 (i,j,k)，h_j 带来的代价是固定的，我们需要尽可能最小化 h_i,h_k 带来的代价。先将这些数中最左边和最右边的数 +1，然后操作中间的数就可以令 h_i,h_k=h_j+1，非常划算。为了最小化最左边和最右边的数操作的代价，可以算出先左后右，先右后左的代价。这是一个求一段前缀/后缀中某个数后继的问题，可以选用自己喜欢的数据结构维护。
然而 h 的值域非常大，令 x 为目前的山谷里的最小值，y 为 x 在所有 h_i 中的后继，将所有山谷里的最小值从 x 加到 y 的过程中，由于需要改变的数的集合不变，可以整体处理，而这个集合只会改变 O(n) 次，故复杂度是 O(n \log n) 的。
部分分在暗示做法。
最关键的一个性质：考虑第 i 个数 h_i 在最后被换到了 p_i 的位置，那么最终状态下，第 p_i 个数是 (-1)^{i-p_i}h_i，且操作次数是 p_i 的逆序对数。
先考虑 |h_i| \neq |h_j| 的部分分，按绝对值从大往小枚举，当前枚举到的数，要么丢到末尾且符号为正，要么丢到开头且符号为负。令 dp(i,0/1) 表示，已经枚举了前 i 个数，开头的数模 2 是什么。转移只需要用 BIT 优化一下计算逆序对。
再考虑 |h_i| \le 1，由于符号翻转很烦，需要一点点的转化去掉它。令初始状态为 a_1,\cdots,a_n，目标状态为 b_1,\cdots,b_n，对于所有奇数（偶数也行）的 i，将 a_i,b_i 取相反数，操作就变成了“交换相邻数，没有符号翻转”（理由：转化前后对于符号的要求均为，若 |i-p_i| 为偶数，需要 a_i,b_{p_i} 符号相同；若 |i-p_i| 为奇数，需要 a_i,b_{p_i} 符号相反）。
在转化后的问题上，需要对于一个 -1,0,1 的序列求出，变成某个序列（中间一段为 0，左右两段 +1,-1 交替排列）所需要的最小交换次数。
先做单组询问：给最终状态用 [1,n] 顺次标号，给初始状态中的标号满足：对于所有 x,y，第 x 个数 y 在两个状态中的标号相同。操作次数就是初始状态标号的逆序对。
对于多组询问需要一点分讨，一个稍微简单的做法是，分 0 左边的数有奇数还是偶数两种情况。对于同种情况，将 0 的区间往右移动两步后，标号序列的变化也仅仅是将两个数的标号移到中间一段 0 的前面，很容易用 BIT 计算逆序对的变化量。
考虑满分做法：dp 状态一样，按绝对值 x 从大到小枚举的时候，将 +x 看成 +1，-x 看成 -1，绝对值小于 x 的看成 0。有时候 0 会很多，但是计算逆序对的时候只需要分别计算：(-1,0),(1,0),(-1,1) 之间的贡献，额外用 BIT 维护 0 的位置即可。
复杂度 O(n \log n)。
令 u,v 为我们选的两个叶子，在点 w 取到所有点到 u,v 路径距离的最大值（即取到题目中 H 的最大值），令 x 为 u,v 路径上到 w 距离最小的点。
枚举 x，将 x 的所有子树（注意定根后不要漏掉上面的那棵子树）按子树内最深叶子的深度从大到小排序。取出前三个子树中最深的叶子，令深度为 a,b,c(a \le b \le c)，最大化 hardness 一定是令 u=a,v=b,w=c，此时 hardness=c(a+b)（理由：hardness 可以写成 ab+ac+bc-(作为u,v的点的乘积)，最小化减去的部分即可）。
计算方案数有点麻烦，先换根 dp 预处理出每个节点子树内和子树外，距离最远的叶子和叶子个数。计数的时候数出 a,b,c 有多少个可选方案，分 a,b 是否相等，b,c 是否相等讨论。
幸运的是，计算取到最大值的方案时不会被重复计算。证明只需要证对于任意取到最大值的 u,v，只有一个合法的 w。若有多个，则将 u,v 其中之一替换成另一个 w，能变的更优。
复杂度 O(n) 或 O(n \log n)，取决于实现，均可过。
对于测试点 1，可以爆搜，复杂度 O((N^2)!poly(N))。
对于测试点 2,6，可以剪十六个小纸片玩，观察发现前若干次操作一定是转矩形的最外面一圈，类似于 UUULLLDDDRRRUUULLLDDDRRR... 的过程，当把 1,2,3,4 转到最上面的时候，剩余部分可以暴力或者用下文方法解。
考虑 bfs，设计一个估价函数，每一层只保留一些可能比较优的状态，可以试试如下几个。
实测和/平方根和比较优秀。
这样子会出现一个现象，目前队列中估价函数最低的会在两个数中反复横跳，每次扰动一步显然是不够的。可以在模 2/3/4=0 的某一轮中删减状态。
需要调一调删除的频率和保留的状态数。
当然估价函数并不是特别合理的，比如有两个相邻但位置相反的数，空格又隔得特别远。其实这种状态是很劣的，但这几种估价都会认为这种状态很优秀。或者说多个路径交错在一起，也是特别劣的，但很难设计函数把它们区分开，欢迎各位来交流更好的估价函数。
题外话：关于多项式复杂度的构造方法，也是我的赛时做法：
. 表示空格，? 表示没被归位的数字）：1 2 . 3 ? ? ? 4
1 2 4 . ? ? 3 ?
所以记录状态时记录两个数的位置和空格的位置，也一定能得到解。
1 2 3 4 5 6 7 8 ? 13 9 ? ? ? ? .
复杂度 O(n^7)。肯定有更优的做法。
但这样构造，我只在测试点 9 得到了 3 分，其余均为 2 分。
直觉上特别违背信息论，因为只能传递 3000 bits，而传递 y_i 已经需要 3000 bits。
假设解密时知道了所有 x_i，那么只需要在加密的时候按 x_i 排序后传递 y_i，正好符合要求。
怎么不传递 x_i 呢？或者将给定的键值对转化成一些固定的 x_i，比如将所有 x_i 变成 [1,n] 的排列。
拉格朗日插值！
由于 n 个键值对 (x,y)，唯一确定了一个 n-1 次多项式，将这个多项式求出来，传递 [1,n] 的点值（传系数也行），解码的时候插值一下，由于插值有除法，可以在模 10^9+7 下算，需要的位数不变。
一个非常直观的结论：换乘一定是从 B_i 大的换到 B_i 小的，也就是说经过的所有点（除了终点），B_i 是递减的。
将所有 i 按 B_i 从大到小排序，令 dp(u) 表示到达点 u 所需的最小代价，转移：dp(u)=\min_{v|B_v \gt B_u}\{ dp(v)+A_v+B_v \cdot dist(u,v)\}。
将 dp(v)+A_v+B_v\cdot dist(u,v) 中，B_v 看成斜率，A_v+dp(v) 看成截距，dist(u,v) 看成自变量 x。考虑点分树，在点分树上的所有点上维护一个凸包，计算完 dp(v) 之后，在点分树上所有 v 的祖先 fa 上的凸包，加入直线 y=B_vx+(B_v \cdot dist(v,fa)+A_v+dp(v))，因为 B 是递减的，用单调栈维护凸包，查询时二分查询 x=dist(u,fa) 处的 y，复杂度 O(n \log^2 n)。
有个小细节，路径上经过的所有点中，终点不保证是 B_i 递减的，需要额外计算最后一步，可以用一样的方法计算。
非常直观的感觉，操作次数不会特别的多，考虑证明上界为 3。
令 a_i 为给定的数组，s_i 为 a_i 的前缀和，令 s_x,s_y 分别为 s_i 的最小值和最大值。
分情况讨论：
若答案为 0，当且仅当所有 a_i \ge 0。
若答案为 1，不妨要么进行一次 1 操作，要么存在一个区间满足前/后缀和 \ge 0，且区间外的所有数 \ge 0。而在区间左右两端加上非负数是不劣的，故只要判断前/后缀和数组是否都 \ge 0。
若答案为 3，直接构造。
若答案为 2，分两种操作类型相同/不同讨论。
若相同，令两次都为 2 操作，我们需要找到一个区间，满足将这个区间替换成前缀数组后，整个序列的前缀数组均 \ge 0。令第一步操作的区间为 [l,r]，则 [1,l-1] 的前缀数组需要 \ge 0，令 l=1，是不劣的，故第一次操作一定是操作一个前缀。枚举这个前缀，需要维护：单点修改，求前缀和数组最小值。用线段树维护前缀和数组，单点修改对应了区间加减，查询对应了全局最小值。
若不同，不妨令第一次为 3 操作，第二次为 2 操作，考虑分治，令当前区间为 [l,r]，中点为 mid，令 a_i 为原数组，s_i 为前缀和。
对于所有 i \in [mid+1,r] 计算：
对于所有 i \in [l,mid] 计算：
一个合法的第一次操作区间 [L,R] 需要满足：
三个限制条件分别令 [1,L-1],[L,mid],[mid+1,n] 三段满足条件。将所有满足第一条限制的 L，和所有 R 搞出来，按 A_R 或 E_L 排序。第三个限制，对于所有 L 可以看成直线 y=(mid-L+1) \cdot x+(D_L+F_L)，对于所有 R 可以看做查询 x=A_R。
复杂度 O(n \log^2 n)。
将每个所有人帽子颜色的状态 u 拆成两个节点 u_0,u_1。若两个状态 x,y 仅有一位 d 不同，不妨令 x 的第 d 位为 0，则在 x_0,y_1 之间连一条无向边，含义是第 d 个人无法区分 x,y 这两个状态，需要给这条边定向：指向 x_0 表示猜 0，指向 y_1 表示猜 1。
定完向后，对于一个度数为 deg 的节点，至少有 \lfloor deg/2 \rfloor 条边指向它。我们可以想到欧拉回路：建立一个虚点，先对于所有度数为奇数的点（一定有偶数个）向这个虚点连边，跑出欧拉路，按照欧拉路定向，每个点入度和出度相等，均为 \ge \lfloor deg/2 \rfloor，符合题意。
复杂度 O(2^NN)。