给定两个大小相等的集合 $A,B$，求满足 $f(i)\not=i$ 的双射 $f$ 的数量。

若 $A=B$ 则为错排问题，所以我们考虑类似地通过递推解决这个问题。

令 $S=A\cap B$，设 $f(n,m)$ 为 $|S|=n,|A|=|B|=n+m$ 时这样的双射 $f$ 的数量。

显然 $f(0,m)=m!$。$n>0$ 时我们令 $t=\inf S$，对所有 $f$ 按照 $f(t)$ 进行分类讨论：

• 若 $f(t)\in S$ 且 $f(t)=f^{-1}(t)$，显然有这种情况下所有合法 $f$ 到 $A,B$ 均去掉 $t,f(t)$ 后所有合法 $f$ 的双射，所以这种情况的方案数为 $(n-1)f(n-2,m)$
• 否则，通过令 $f^{-1}(t)$ 映射到 $f(t)$，可以得到所有合法 $f$ 到 $A,B$ 均去掉 $t$ 后所有合法 $f$ 的双射，所以这种情况的方案数为 $(n+m)f(n-1,m)$。

由此可以得到递推式 $f(n,m)=(n-1)f(n-2,m)+(n+m)f(n-1,m)$。可见合法的状态只有 $O(n)$ 种。

将该组合游戏进行拆解，某个 DAG 上该游戏先手必胜等价于 $1,2$ 节点的 SG 值不相等。

某个节点的 SG 值为其所有后继节点的 $\mathrm{mex}$，也即某个节点的 SG 值为 $x$ 当且仅当其向 SG 值分别为 $[0,x)$ 的节点各连了至少一条边，并且没有连向 $x$ 的边。

这提示我们从小到大，每次考察 SG 值为 $x$ 的点的集合。SG 值大于 $x$ 的所有节点必须向这个集合中至少连一条边；这个集合中的节点不能向集合中其它节点连边；SG 值小于 $x$ 的所有节点连边无限制。

状压 DP 即可。

设初始局面只有点 $x$ 被染色，最后被染色的点集为 $f(x)$，那么显然起初有多个点 $x_1,x_2,\cdots,x_m$ 染色，最终被染色的点集为 $f(x_1)\cup f(x_2)\cup\cdots\cup f(x_m)$。

于是我们探寻 $f(x)$ 会包含哪些节点。

对于点 $i<x$，它被染色当且仅当存在点 $j$ 不在 $x$ 左侧，并且满足 $V_j<V_i$。这样 $i$ 要么先与 $x$ 相遇，被染色；要么先与 $j$ 相遇，此时 $j$ 一定在 $x$ 左侧，即 $j$ 一定被染色，于是 $i$ 被染色。显然不存在其它染色情况。

同理，对于点 $i>x$ 它被染色当且仅当存在点 $j$ 不在 $x$ 右侧，并且满足 $V_j>V_i$。

我们把所有点按照 $X$ 排序后重新编号。设 $\mathrm{pmx}_i=\max_{i\in[1,i]}V_i$ 和 $\mathrm{smn}=\min_{i\in[i,n]}V_i$。于是 $f(x)=\{i\mid i<x\land V_i<\mathrm{smn_i}\}\cup\{i\mid i>x\land V_i>\mathrm{pmx_i}\}\cup\{x\}$。

于是考虑对初始局面进行 DP。设 $g_i$ 为最靠右的初始被染色的点，且能够最终将 $[1,i]$ 中所有点都染上色的初始局面数。

那么由 $g_j$ 到 $g_i$ 的转移只需要保证 $(i,j)$ 中所有节点都染上色即可，即 $(i,j)$ 中不存在点 $t$ 使得 $V_t\in[\mathrm{pmx}_j,\mathrm{smn}_i]$。考虑到 $\mathrm{pmx},\mathrm{smn}$ 均单调，可以使用双指针维护。

考虑到序列的后缀颜色数随着后缀长度增加单调不减，而非空区间内的颜色数只可能有 $1,2,3$ 种，所以尝试维护后缀颜色数出现差异的左端点位置，即从右向左第一次出现新颜色的位置、第二次出现新颜色的位置。

对前缀 $[1,i]$ 进行 DP，校验所有右端点为 $i$ 的限制，对符合限制的状态向后贡献即可。

从左到右依次考虑所有端点，进行决策。

为了便于处理线段重叠的情况，设 DP 状态 $f_{i,j}$ 为前 $i$ 个端点的所有决策中，覆盖点 $j$ 以左的部分最多有多长。

分类讨论这 $i$ 条线段，是否覆盖到了 $a_i$ 以右的点。

没有覆盖的话，$j=a_i$ 时的答案应该由 $j=a_i-l_i$ 的答案转移而来。

否则我们枚举右端点最靠右的线段 $k$，显然此时 $(k,i]$ 中的线段向右延伸一定不优于全部向左延伸。设 $(k,i)$ 中所有线段向左延伸的左端点为 $t$，那么 $j=a_k+l_k$ 时的答案应当由 $j=t$ 的答案转移而来。

此时我们处理完了 $j$ 恰好落在被覆盖的最靠右的点的情形。那么对此从左向右令 $f_{i,j}\leftarrow\max(f_{i,j},f_{i,j-1})$，再从右向左地依次令 $f_{i,j}\leftarrow\max(f_{i,j},f_{i,j+1}-1)$。即可。这样做等效于将 $j$ 处的值改为 $\max(\max_{k\le j}f_{i,k},\max_{k>j}f_{i,k}-k+j)$，如果 $i$ 没有被覆盖，那么会取前者，否则会取后者（因为 $f_{i,j+1}-f_{i,j}\in[0,1]$）。

同一个位置上的数看似可能被多个 $c$ 所限制，但实际上真正限制它的只有所有涉及到它的 $c$ 中最大的。

那么我们转而考察某个极长的 $c_i$ 相等的区间 $[i,j]$ 会对哪个区间做出什么样的限制。

如果该区间的 $c$ 大于其左侧区间，那么它所限制的区间的左端点为 $i$；否则它所限制区间的左端点为 $i+K-1$，并且该区间一定以 $c$ 开头。特别地，第一个区间的开头为起始位置。

如果该区间的 $c$ 大于其右侧区间，那么它所限制的区间的右端点为 $j+K-1$；否则它所限制区间的右端点为 $j$，并且该区间一定以 $c$ 结尾。特别地，最后一个区间的结尾为终止位置。

---

接下来需要解决这样的问题：求长度为 $n$，任意长为 $k$ 的区间最小值都为 $c$ 的序列的数量。

不难发现这样的要求等价于，每个值不小于 $c$，并且任意长为 $k$ 的区间中均包含至少一个 $c$。

于是 DP，用前 $n-1$ 个数合法，最后一个数任意填的方案数，减去前 $n-1$ 个数合法，长为 $k$ 的后缀中不出现 $c$ 的方案数即可。

从前往后依次考虑每个段，不难发现，某个段内要么不表演，要么在不与之前的表演冲突的前提下，尽可能多地表演，即不需要迁就后面的段而让当前的段少表演，否则将后面段的表演移到前面段来，一定不劣。

既然如此，我们只需要 DP 求前 $i$ 段中最多唱多少首歌，设为 $f_i$；在唱最多歌的基础上，最早什么时候结束，设为 $g_i$。

暴力转移是 $O(n^2)$ 的。

考虑满足 $g_j\le l_i-t$ 的转移 $j\to i$，$i$ 段的决策一定是从 $l_i$ 开始唱歌，所以在只从最后一个这样的 $j$ 更新，一定不劣。

而对于 $g_j>l_i-t$ 的所有转移 $j\to i$，每个 $j$ 在整个过程中最多进行一次这样的转移，所以可以暴力做。

不难发现一个性质，如果某个方案中老鼠 $i,j$ 分别躲进了洞 $u,v$ 中，$x_i<x_j$ 而 $p_u>p_v$，显然调整为让 $i$ 躲进 $v$，$j$ 躲进 $u$，该方案一定不会变劣。因此，将老鼠按照起点所在的位置划分为几个连续段，这些连续段从左往右依次匹配从左往右的洞，一定不劣。

考虑朴素 DP，设 $f_{i,j}$ 表示前 $i$ 个洞匹配前 $j$ 个老鼠，老鼠需要走的总长度最小值。有

$$\displaylines{\begin{aligned} f_{i,j}&=\min_{k=j-c_i}^j\left\{f_{i-1,k}+\sum_{k<t\le j}|x_t-p_i|\right\}\\ &=\min_{k=j-c_i}^j\{f_{i-1,k}+s_{i,j}-s_{i,k}\}\\ &=s_{i,j}+\min_{k=j-c_i}^j\{f_{i-1,k}-s_{i,k}\} \end{aligned} }$$

其中 $s_{i,j}$ 表示 $\sum_{t\le j}|x_t-p_i|$，并且 $j$ 增大的过程中，$k$ 的合法取值区间单调右移，使用优先队列优化到 $O(nm)$。

这道题的方案限制是在树上做出的，所以我们不免会想到对子树考虑是否可以设计状态使其具有最优子结构，并且便于转移。

发现这些限制在儿子向父亲转移时具有极良好的性质：

• 根和子树内其它节点不在同一块中，单独成块。
• 以两个儿子为根的子树合并时，两边各取一个互不冲突的集合，并起来亦不冲突。

那么下面贪心合并的方案是显然的：两个子树分别按照段内最大值（即该段贡献）从小到大排序，然后两个子树一一对应合并，分段较多的子树剩下的段不合并。

还需要证明最优子结构性，即在儿子子树的最优方案中被分到同一段的元素，父亲处被分到同一段一定不劣。

我们用某个方案中所有段的大小升序排序后得到的序列代表它。如果两个方案 $a,b$ 满足对于任意位置 $i$ 都有 $a_i\le b_i$，我们称方案 $a$“严格不劣于”$b$。不难发现这样的关系构成了偏序，我们证明同一个子树内所有方案构成的偏序集的极小值是唯一的。

叶子节点本身构成的子树只有一种方案，所以极小值唯一；两种极小值唯一的偏序集按照上述方法进行合并，如果 $x$ 严格不劣于 $a$，$y$ 严格不劣于 $b$，并且 $x\not=a$ 或 $y\not=b$，那么显然 $x,a$ 合并后严格不劣于 $y,b$，并且两者不相等。

朴素的 DP 是，设 $f_{i,j}$ 为 $a$ 长为 $i$ 的前缀，最后一处截断位于 $j$ 时的最小运行时间。

转移为

$$\displaylines{f_{i,j}=(s_i-s_j)^2\min_{s_k\le2s_j-s_i}f_{j,k} }$$

其中 $s_i=\sum_{j=1}^ia_j$。

不难发现 $f_{i,j}$ 在 $j$ 有意义的区间中单调不增。

考虑数学归纳法，$i=0$ 时成立。

设 $t_i$ 为长度为 $i$ 时所有合法的阶段方案中最后一个阶段位置的最大值。显然 $t_{i+1}\ge t_i$

假设单调性对于 $f_0,f_1,f_2,\cdots,f_{i-1}$ 均成立，考虑

$$\displaylines{\begin{aligned} f_{i,j+1}&=(s_i-s_{j+1})^2+f_{j+1,t_{j+1}}\\ &\le(s_i-s_{j+1})^2+f_{j+1,t_j}\\ &=(s_i-s_{j+1})^2+(s_{j+1}-s_{t_j})^2+f_{t_j,t_{t_j}}\\ &=(s_i-s_j-a_j)^2+(s_j-s_{t_j}+a_j)^2+f_{t_j,t_{t_j}}\\ &=(s_i-s_j)^2+(s_j-s_{t_j})^2+f_{t_j,t_{t_j}}-2a_j((s_i-s_j)-(s_j-s_{t_j})-a_j)\\ &=(s_i-s_j)^2+(s_j-s_{t_j})^2+f_{t_j,t_{t_j}}-2a_j((s_i-s_{j+1})-(s_{j+1}-s_{t_j})+a_j)\\ &\le(s_i-s_j)^2+(s_j-s_{t_j})^2+f_{t_j,t_{t_j}}\\ &=(s_i-s_j)^2+f_{j,t_j}\\ &=f_{i,j} \end{aligned} }$$

由第二归纳法，单调性成立。

于是我们只关心 $f_{i,t_i}$ 的值。$t_i$ 具有单调性，可以双指针求得。