T1

当 $n=1$ 时，整个魔方只有一个小方块，答案为 $1$。

当 $n\ge 2$ 时，先计算整个 $n\times n\times n$ 立方体的体积，再减去内部边长为 $n-2$ 的空心部分：

$$\text{ans}=n^3-(n-2)^3.$$

按照公式逐组计算即可。

时间复杂度：$O(T)$。

T2

我们考虑维护三个量：

• 当前覆盖区间的左端点 $l$；
• 当前覆盖区间的右端点 $r$；
• 已经吃掉的小鱼数量 $sum$。

初始时 $l=r=s$。依次处理每个 $x_i$：

1. 若 $x_i<l$，区间整体左移，令 $l--$、$r\leftarrow r--$；
2. 若 $x_i>r$，区间整体右移，令 $l++$、$r++$；
3. 否则小鱼位于区间内，将 $sum$ 加一，并令$$l = \max(1,l-1),\qquad r = \min(m,r+1).$$

可以发现当 $x_i<l$ 时，由 $x_i\ge1$ 可知 $l>1$，因此左移不会越界；右移同理。

时间复杂度：$O(n)$。

T3

制作失败不会改变机器颜色。因此，无论如何排列贴纸，所有成功贴纸的颜色顺序都只能是

$$s,s+1,\ldots,k,1,2,\ldots$$

的一个前缀。

反过来，只要库存足以提供这个前缀，就可以按照前缀顺序依次取出对应颜色的贴纸，使它们全部成功。于是问题等价于：给定每种颜色的贴纸数量，求上述无限循环序列最多能取多长的前缀。

我们可以用 map 来统计每种颜色的贴纸数量。从颜色 $s$ 开始模拟：如果当前颜色仍有贴纸，就消耗一张并转到下一种颜色；否则停止。

每成功一次都会消耗一张贴纸，所以循环至多执行 $n$ 次。

时间复杂度：$O((n+k)\logn)$。

T4

子任务 1

如果当前所有值两两不同，那么最小值的位置唯一。设当前最小值为 $x$、最大值为 $M$，操作后新值为 $x+M>M$，它会成为新的唯一最大值，所以所有值仍然两两不同。

因此，在子任务 1 中，整个操作序列是确定的。可以用有序集合维护当前最小值和最大值，正向模拟直到到达目标，或某个位置超过对应的 $b_i$。

若执行了 $q$ 次操作（不难证明 $q$ 大致是 $O(n log 10^9)$），时间复杂度为 $O((n+q)\log n)$，空间复杂度为 $O(n)$。

子任务 2

考虑一次操作前后的状态。被选择的值原来是某个最小值 $x$，操作前最大值为 $M$，操作后它变成

$$x+M>M.$$

因此，每次操作后，刚刚被修改的位置一定是唯一最大值。

这使得逆向过程没有选择：

1. 当前状态的唯一最大值所在位置，一定是最后一次被操作的位置；
2. 其余元素没有变化，所以操作前的最大值就是当前状态中除它以外的最大值，也就是当前第二大值；
3. 用当前最大值减去第二大值，就能还原该位置操作前的值。

利用这个方法，我们只需要判断操作时是否有 $b[i] = a[i]$，如果有说明还原过程已经结束。以及还原过程中是否有最大值变成最小值这种情况，如果不是，那么这个还原同样是不合法的。

判断完最大值后只需要判断整体的数组是否相同即可。

设逆向执行了 $q$ 次。时间复杂度为$O((n+q)\log n)$。

T5

设

$$d=(b-a)\bmod m,\qquad d\ne 0.$$

设 A 表示第一个操作（移动 A 棋子），B 表示第二个操作（移动 B 棋子）。可以发现连续操作两次同一枚棋子，相当于什么都没做。因此最短方案中不可能出现 AA 或 BB，操作一定交替进行的。

又因为整体平移不影响操作，可以把初始状态 $(a,b)$ 平移成$(0,d)$，目标就变成 $(d,0)$。

考虑从 A 开始交替操作：

$$(0,d) \xrightarrow{A}(2d,d) \xrightarrow{B}(2d,3d) \xrightarrow{A}(4d,3d) \xrightarrow{B}(4d,5d)\cdots$$

容易归纳得到，操作 $k$ 次后：

$$\begin{cases} ((k+1)d,kd),&k\text{ 为奇数},\\ (kd,(k+1)d),&k\text{ 为偶数}. \end{cases}$$

如果从 B 开始，同理：

$$\begin{cases} (-(k-1)d,-kd),&k\text{ 为奇数},\\ (-kd,-(k-1)d),&k\text{ 为偶数}. \end{cases}$$

所有坐标都在模 $m$ 意义下理解。

对于奇数 $k$，无论从 A 还是 B 开始，要到达 $(d,0)$，条件都恰好是

$$kd\equiv 0\pmod m.$$

设

$$g=\gcd(m,d).$$

那么满足 $kd\equiv0\pmod m$ 的最小正整数是

$$q=\frac m g$$

因此我们需要一个“奇数的 $q$ 的倍数”。

• 若 $q$ 是奇数，最小就是 $k=q$；
• 若 $q$ 是偶数，它的所有倍数都是偶数，不可能。

还要排除偶数 $k$ 有没有可能。以下是偶数 $k$ 不满足条件的证明：

以从 A 开始为例，偶数 $k$ 时要求

$$kd\equiv d,\qquad (k+1)d\equiv0,$$

即

$$(k-1)d\equiv0,\qquad(k+1)d\equiv0.$$

所以

$$q\mid(k-1),\qquad q\mid(k+1).$$

于是

$$q\mid\gcd(k-1,k+1).$$

由于 $k$ 是偶数，$k-1,k+1$ 都是奇数且相差 $2$，它们的最大公约数只能是 $1$。因此 $q=1$，但 $d\ne0$，所以 $q>1$，矛盾。

从 B 开始完全相同。因此偶数步不成立。

所以最终结论为：

$$\boxed{ q=\frac{m}{\gcd(m,b-a)} }$$

若 $q$ 为奇数，答案是 $q$，否则答案是 $-1$。

时间复杂度为 $O(T\log m)$。

T6

设某种颜色出现的两个顶点为 $u,v$。

如果选择顶点 $r$ 作为根，那么这两个点的深度分别为

$$\operatorname{dist}(r,u),\qquad \operatorname{dist}(r,v).$$

因此，$r$ 对这一种颜色合法，当且仅当

$$\operatorname{dist}(r,u)\ne \operatorname{dist}(r,v).$$

所以问题的关键是：对于树上的两个点 $u,v$，求哪些顶点到它们的距离不同。

记 $D=\operatorname{dist}(u,v)$，那么会有以下两种情况：

情况 1：$D$ 为奇数

假设存在某个顶点 $r$，满足

$$\operatorname{dist}(r,u)=\operatorname{dist}(r,v).$$

在树上有

$$\operatorname{dist}(r,u)+\operatorname{dist}(r,v) \equiv \operatorname{dist}(u,v) \pmod 2.$$

左边因为两项相等，一定是偶数，因此右边也必须是偶数。

这与 $D$ 为奇数矛盾。

所以，当 $u,v$ 之间距离为奇数时，不存在到二者距离相等的顶点。

即：对于这一种颜色，所有顶点都是合法根。

---

情况 2：$D$ 为偶数

设 $D=2k$，此时路径 $u\to v$ 上存在唯一一个中点 $m$，满足

$$\operatorname{dist}(m,u) = \operatorname{dist}(m,v) = k.$$

设路径上与 $m$ 相邻、分别朝向 $u,v$ 的两个点为 $x,y$：

$$u\cdots x-m-y\cdots v.$$

将边 $(x,m),(m,y)$ 删除后，整棵树被分成三个部分：

• 包含 $u$ 的连通块；
• 包含 $v$ 的连通块；
• 包含 $m$ 的连通块。

下面分析根 $r$ 分别位于这些部分时的情况。

如果 $r$ 位于包含 $m$ 的连通块，那么从 $r$ 前往 $u,v$ 的路径都会经过 $m$，所以

$$\operatorname{dist}(r,u) = \operatorname{dist}(r,m)+\operatorname{dist}(m,u),$$$$\operatorname{dist}(r,v) = \operatorname{dist}(r,m)+\operatorname{dist}(m,v).$$

由于

$$\operatorname{dist}(m,u)=\operatorname{dist}(m,v),$$

因此

$$\operatorname{dist}(r,u)=\operatorname{dist}(r,v).$$

这些顶点都是不合法的。

反之，如果 $r$ 位于包含 $u$ 的连通块，那么它相对于中点 $m$ 更偏向 $u$ 一侧，因此到 $u$ 和 $v$ 的距离一定不同。

包含 $v$ 的连通块同理。

所以当两个同色顶点之间距离为偶数时，合法根恰好是中点朝 $u$、$v$ 两个方向的两个连通块。

---

因此对于每一种颜色，我们都可以求出它对应的合法根集合：

• 若两个同色点距离为奇数，合法集合为整棵树；
• 若距离为偶数，合法集合为删除中点两侧的边后，包含两个端点的两个连通块。

我们可以对每个顶点记录：

$$cnt_r= \text{有多少种颜色认为 }r\text{ 是合法根}.$$

总共有

$$\frac n2$$

种颜色，因此最终

$$r\text{ 合法} \iff cnt_r=\frac n2.$$

问题于是变成：如何快速对删除一条边后某一侧的整个连通块进行整体加。

任选一个顶点作为辅助根，将原树转化为有根树。

预处理每个顶点的：

• 深度；
• 子树大小；
• DFS 序；
• LCA 信息。

DFS 序具有一个性质：一个顶点的整棵子树在 DFS 序中对应一个连续区间。

设顶点 $u$ 的 DFS 序为 $\mathrm{dfn}_u$，子树大小为 $\mathrm{sz}_u$，那么其子树对应区间为

$$[\mathrm{dfn}_u,\, \mathrm{dfn}_u+\mathrm{sz}_u-1].$$

现在考虑删除一条边 $(a,b)$。

由于树已经固定了辅助根，因此 $a,b$ 中必然一个是另一个的父亲。

如果我们需要的连通块位于儿子一侧，那么它恰好是一棵子树，对应一个连续区间。

如果需要的是父亲一侧，那么它等于

$$\text{整棵树}-\text{儿子的子树},$$

也可以表示为整棵树加一次，再减掉一个子树区间。

因此：删除任意一条边后得到的任意一侧连通块，都能用常数个 DFS 序区间表示。

使用差分数组，就可以对这些区间进行 $O(1)$ 修改。

现在的问题就剩下：如果求出 $x,y,m$？

对于每一对同色顶点 $u,v$，首先利用 LCA 求出距离

$$D= \operatorname{dep}_u+ \operatorname{dep}_v- 2\operatorname{dep}_{\operatorname{LCA}(u,v)}.$$

若 $D$ 为奇数，直接对整棵树贡献一次。

若 $D=2k$，则需要找到路径上的三个连续顶点：

$$x-m-y,$$

其中 $m$ 是路径中点。

利用倍增，可以在 $O(\log n)$ 内找到路径上距离 $u$ 分别为

$$k-1,\quad k,\quad k+1$$

的三个顶点，它们正好就是 $x,m,y$。

然后分别将：

• 删除边 $(x,m)$ 后 $x$ 所在的连通块；
• 删除边 $(y,m)$ 后 $y$ 所在的连通块；

整体贡献 $1$。

这两个连通块的并集就是这一种颜色对应的所有合法根。

如何计算从 $u$ 出发距离为 $t$ 的点，以下是一种思路：

1. 若 $\operatorname{dep}_u - \operatorname{dep}_{\operatorname{LCA}(u,v)} \ge t$，那么直接从 $u$ 往上跳 $t$ 步即可，利用倍增数组可以很方便求出。
2. 若 $\operatorname{dep}_u - \operatorname{dep}_{\operatorname{LCA}(u,v)} < t$，此时对应点在 $v$ 往上的链中，故从 $v$ 往上跳 $D - t$ 步即可。

时间复杂度为 $O(n \log n)$。