搬题人：
验题人：
原题：
你可以在原题中找到非中文的题解，中文题解会稍后发布。
这是我第一次给 pjudge 搬题，不足知处请多多包涵。
你可以在本帖中尽情开喷，我会在下一场 pnr 中改进。
令操作结束后序列是 $y_1,y_2,\cdots,y_n$，容易发现，把 $x,y$ 分别排序，将 $x_1$ 变为 $y_1$，将 $x_2$ 变为 $y_2$ ……，是最优的。
于是问题变成了，把 $x_i$ 升序排列后，要求对于所有 $i(2 \le i \le n),x_i-x_{i-1} \ge d$，求最少操作次数。
考虑其差分序列，直接套用 UOJ-雪灾与外卖 的模拟费用流算法，能得 $70$ 分。
再次转化，将 $x_i$ 减去 $(i-1)d$，问题就变成了让 $x_i$ 不降，求最少操作次数，这个能直接做到 $O(n \log n)$。
先拆一下贡献，对于每条边，将它的经过次数加到答案里，最后答案加上 $2(n-1)$，就是真正的答案。
考虑把 $u$ 挂在 $v$ 上的过程，令 $S$ 表示 $u$ 所在连通块的点集，则 find(u) 到 find(v) 这条边的经过次数为：$-2(|S|-1)-1+\sum_{x \in S} deg(x)$。令这一坨式子为一个连通块的权值，显然，我们应该把 $u,v$ 所在连通块中，权值较大的挂在权值较小的上面。
继续观察，假设 $u$ 所在连通块的权值比 $v$ 大，那么把 $v$ 里面的点一个一个挂到 $u$ 上一定是更优的。
枚举起点，将树定根在起点，问题变成了，每个点有一个权值，将 $0,1, \cdots, n-1$ 放到每个点上，要求父亲的数大于儿子，最大化每个点上权值乘上数的和。这是经典的问题，每次取权值最大的，它上面的数一定是父亲的 $-1$，将它和父亲合并就行，新权值设为连通块内的平均数。
复杂度 $O(n^2 \log n)$。
考虑最朴素的 dp：$dp(i)$ 表示前 $i$ 个数的最大价值，转移 $dp(i)+mex(i+1,j) \cdot sum(i+1,j) \rightarrow dp(j)(j-i \le k)$。
从 $1$ 到 $n$ 依次计算 dp 值，令当前算到的位置为 $i$，先维护每个位置到 $i$ 这一段的 $mex$，直接开珂朵莉树维护其连续段，能分析出总共只有 $O(n)$ 次连续段的变化。
转移考虑根号重构，令 $B=\lfloor\sqrt{n} \rfloor$，若 $i \bmod B=0$，则重构 $[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)$。