真让我给干出来了我去。已加入“超级无敌神仙炫酷无敌原神大王”豪华套餐。

首先考虑 $k=0$ 的情况，我们在置换环上考虑，每次操作为选择若干对不交点对，并让每对点交换出边，最终目标是全部为自环。

首先考虑计算 $f(A)$。

引理：对于一个 $n(n\ge 3)$ 元环，可以一次操作将其变为若干二元环和自环。

证明：不妨将 $n$ 元环按有向边方向编号 $1$ 到 $n$。那么构造方案 $(1,n),(2,n-1),...$ 即可（若 $n$ 为奇数会剩下一个点不操作），证毕。

而二元环可以一步变为两个自环，于是 $f(A)\le 2$。具体的，若原图只有自环，则 $f(A)=0$；若原图只有二元环，则 $f(A)=1$；否则，$f(A)=2$。

接下来考虑计算 $g(A)$。

对于 $f(A)\le 1$ 的情况显然 $g(A)=1$。下面只考虑 $f(A)=2$ 的情况。

通过大量手玩，我们可以发现多元环的变化流程都能被概括为：$n (n\ge 3)$ 元环 $\to$ 若干二元环 $\to$ 若干自环。

由于第二步的操作是固定的，我们注重考虑第一步的方案数。首先注意到在两个环长不同的环间操作一定不能全部拆解为二元环，那么我们只需考虑在同种环间的操作。

对于 $n(n\ge 3)$ 元环，“拆解”有两种形式：

1. 一个 $n$ 元环自主拆解，有 $n$ 种方案。对于 $n$ 为奇数，同引理的证明的构造方式，可任选不操作的点。对于 $n$ 为偶数，引理证明的构造有 $\frac{n}{2}$ 种方案，再加上 $(2,n),(3,n-1),...$ 这种构造（$1$ 和 $\frac{n}{2}+1$ 都不操作）也有 $\frac{n}{2}$ 种方案，故共有 $n$ 中方案。

2. 两个 $n$ 元环配对，有 $n$ 种方案。记两个环的编号分别为 $x_i,y_i$，那么构造操作 $(x_1,y_n),(x_2,y_{n-1}),...,(x_n,y_1)$ 即可，由于 $y$ 可以旋转 $n$ 次，故共有 $n$ 种方案。

那么如果我们有 $m$ 个 $n$ 元环，方案数记作 $f_{n,m}$。考虑最后一个环是否去配对，有递推：

$$f_{n,m}=n[f_{n,m-1}+(m-1)f_{n,m-2}]$$

对于二元环，由于它不需要专门去变为二元环，它的“拆解”有三种形式：

1. 第一步变为自环，第二步不操作。

2. 第一步不操作，第二步变为自环。

3. 第一步找另一个二元环配对，操作后仍为两个二元环，第二步变为自环。

通过计算发现，最终的式子与 $n\ge3$ 时的形式一样。

对于自环，与 $n\ge3$ 时的情况类似，最终的式子也一样，留做练习。

由于每种环长是独立的，对每种环长计算方案数并相乘即为答案。至此，我们得到了一个复杂度 $O(nk!)$ 的做法。

接下来的优化是相对容易的。

观察每个未知点所在的联通块，它一定是一条链，其中未知点为链尾，其他未知点只能连向链首。那么我们可以将它视作一个带点权的大点，这样就转化为了 $k$ 个大点之间相互的连边情况。

注意到我们只关心最终环的集合，而不关心其内部的连边方式，那么我们只需要枚举这 $k$ 个大点的划分即可，共有 $bell(k)\le 4213597$ 种，可以接受。

考虑一种划分 $P$，那么其对应排列的方案数为 $\prod_{x\in P}(x-1)!$，累加答案时作为附加系数即可。

对于这新形成的 $O(k)$ 的环，我们考虑直接去维护它们的加入。具体的，对于原图中完整的环，它们一定不包含未知点，所以是固定的，我们预处理它们的答案，以及每个环长的出现次数 $cnt_i$。当加入一个新环时，直接将答案乘上 $\frac{f_{i,cnt_i+1}}{f_{i,cnt_i}}$ 即可。由于我们不能迅速求一个 $f_{i,j}$，但注意到新的 $cnt_i' \le cnt_i+k$，那么我们只需要预处理出 $f_{i,cnt_i},...,f_{i,cnt_i+k}$ 即可，由于我们可以递推求 $f$，那么这是简单的。

至此，我们得到了复杂度 $O(bell(k)k+nk)$ 的做法。

这不是一篇题解，只是偶然发现大多数提交的复杂度都是错的。

其实只是少了一个剪枝：对所有搜索得到的二元组 $(state,sum)$ 去重。

以下记 $N=2n$。

如果不去重，考虑一组数据满足 $a_i=1$。此时前一半中 $sum=i$ 的状态有 $[x^i](1+x+x^{-1})^n=[x^{i+n}](1+x+x^2)^n$ 个，记作 $f_i$。

由于我们是对于每一个后一半的状态，遍历所有前一半与之相等的状态，那么总遍历量为 $\sum_i{f_i^2}$。查一下 OEIS 发现，这个东西是 $O(\frac{3^{2n+0.5}}{2\sqrt{2\pi n}})$ 也就是 $O(\frac{3^{N+0.5}}{2\sqrt{\pi N}})$ 的，其实不比 $O(3^N)$ 的暴力优多少，证明在link。

然而如果去重了，一个粗略的上界是，对于后一半的 $3^n$ 个状态，前一半中最多有 $2^n$ 个状态与之对应，那么就是 $O(6^{\frac{N}{2}})$ 的。此时也能看出，某谷上一堆说复杂度是 $O(3^{\frac{N}{2}})$ 的题解全是瞎扯。

值得注意的是，官方其实还给出了一种 $(1+\sqrt{1.5})^N$ 的做法，奈何我英语不好看不懂。链接是link。

幸せな明日を願うけど 底なしの孤独をどうしよう

もう うめき声しか出ない  わたし ぎゅうぐらりん

强度最低的一集。

考虑一个点 $(p_1,...,p_k)$ 的距离应该怎么算。

不难发现只可能是他们奇/偶最短路的最大值。也就是在距离最大的点到达前，其他所有的点都在某条边上来回横条。

记 $f_{u,0/1}$ 表示点 $u$ 的偶/奇最短路，那么答案就是

$$\sum_{S=\{p_1,...,p_k\}}{\min(\max_{u\in S}(f_{u,0}),\max_{u\in S}(f_{u,1}))}$$

既有min又有max，不是很好算。考虑min-max容斥，则答案为

$$\sum_S{\max_{u\in S}(f_{u,0})}+\sum_S{\max_{u\in S}(f_{u,1})}-\sum_S{\max_{u\in S}(\max(f_{u,0},f_{u,1}))}$$

注意到三者完全等价，我们只考虑第一项。

考虑将 $u$ 按 $f_{u,0}$ 升序排序后依次扫，那么问题转化为：

每次往某个组加入一个点，求从每个组中各选出一个点的方案数。

预处理逆元，容易做到线性复杂度。

あがいた梦を捨てて揺れる今日は眠って誤魔化せ

失くした言葉を知らないなら　各駅停车に乗り込んで

非常好凸包题，我不会一点。

首先尝试将答案写的形式化一点。令路径依次经过 $(i,a_i)$，则 $a_0=1,a_x=y,a_i\le a_{i-1}$，答案为

$$\sum_{i=1}^{x-1}{C_{a_i}}+\sum_{i=1}^{x}{(a_i-a_{i-1})i^2} =x^2y-1 +\sum_{i=1}^{x-1}{C_{a_i}-(2i+1)a_i} $$

令 $f_{i,j}$ 表示 $a_i=j$ 时的最小答案，根据斜率优化，决策点应该在 $(j,c_j)$ 的下凸包在斜率 $2i+1$ 的切点。

而我们注意到，随着 $i$ 的增大，$2i+1$ 也增大，那么决策点会单调右移。

如果从 $f_{x,y}$ 开始倒序模拟决策过程，那么就是在 $1\sim y$ 的下凸包上，先找到斜率 $2x+1$ 的切点 $p$，之后不断在 $p$ 原地决策，直到 $2i+1$ 小于 $p$ 与 $p-1$ 之间的斜率后，决策点会变为 $p-1$，然后重复……

注意到除了最开始的 $p$，再往后的决策是固定的，可以直接预处理贡献。而 $p$ 可以凸包二分求出，$p$ 的贡献也是容易计算的。

对于多组询问，注意到不同的只有 $y$ 的限制。考虑将询问离线挂到 $y$ 上，在维护到 $1\sim y$ 的凸包时计算答案。

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

君よ いっそいっそ いなくなれ

変わらない このままなら

显然题中生成的BST就是笛卡尔树，但是如果因此就往子树合并类的DP想的话就寄了（比如我）。

正确的做法是，将点的深度转化为祖先的个数，进而转化为每个点成为它祖先的方案数。即

$$Ans_u=\sum_v{\sum_{BST} [v\in anc(u) ]}$$

而 $ [v\in anc(u) ]$ 的充要条件是 $v$ 是 $u,v$ 间的最小值。

如果不考虑 $(u,v)$ 的限制，计算恰有 $k$ 个逆序对的排列数是经典的。令 $f_{i,j}$ 表示 $i$ 个数的排列，已有 $j$ 个逆序对的方案数，枚举 $p_i$ 与前 $i-1$ 位的相对大小，有

$$f_{i,j}=\sum_{k=0}^{i-1} f_{i-1,j-k}$$

这是可以写作生成函数的，令 $F_i=\sum f_{i,j}x^j$，有

$$F_n=\frac{\prod_{i=1}^n(1-x^i)}{(1-x)^n}$$

这允许我们 $O(n^3)$ 的计算总方案数。

现在有了 $(u,v)$ 的限制，先考虑 $u>v$ 的情况。

注意到上面的DP实际上是在往排列中一个一个塞数，而往最前端塞和最后端塞实际上是等价的。

那我们可以先将 $u,v$ 间的数先塞完，那么其它数就跟正常一样的。而增加的限制无非就是在塞 $v$ 的时候令 $k=0$，因为 $v$ 最小，无法产生逆序对。记 $L=u-v+1$，那么我们只用撤销第 $L$ 次转移，即

$$G=\frac{\prod_{i=1}^n(1-x^i)}{(1-x)^n} \frac{1-x}{1-x^L}$$

那么当前的贡献就是 $[x^k]G$。

上面的式子直接算的话是 $O(n^4)$ 的。

我们可以先预处理 $\prod_{i=1}^n(1-x^i)$，并递推求出 $(1-x)^{n-1}G$，然后计算 $[x^k]G$，就可以做到 $O(n^3)$了。

对于 $u<v$ 的情况，无非就是在塞 $v$ 的时候令 $k=L-1$，做法是类似的，不再赘述。

注意到还有 $u=v$ 的贡献，其实就是没有限制的方案数。

于是总时间复杂度 $O(n^3)$。

我等必将复起,古木已发新枝。

前置是Pro3575。

首先把二分图判掉。

回顾一下我们的连边方式可以发现，图中的边只有三类：

1. $(x-1,y-1) \to (x,y)$.

2. $(x-1,y+1) \to (x,y)$.

3. $(x,x+1) \to (x,x+1)$.

显然，每层的方案数互不影响，于是我们可以逐层计算，最后乘在一起即可。

根据有关链头的分析，我们不难得到一个DP：

令 $f_{i,j}$ 表示考虑前 $i$ 个点，且第 $i$ 个点向右留了 $j$ 个链头的方案数。

考虑从 $f_{i-1,k}$ 转移到 $f_{i,j}$。那么 $i$ 中的 $j$ 个点继承前面的链头，剩下 $cnt_i-j$ 个点去连 $fa_i$，那么有

$$f_{i,j} \gets f_{i-1,k} C_{cnt_i}^{j} (2^{cnt_{fa_i}}-1)^{cnt_i-j} g(cnt_{i-1},k,cnt_i,j)$$

其中 $g(n,x,m,y)$ 表示在数量分别为 $n,m$ 的两组点之间连边，使得第一组的前 $x$ 个点以及第二组的前 $y$ 个点都有连边的方案数。

枚举 $x$ 个点中不合法的个数进行容斥，得到

$$g(n,x,m,y)=\sum_{i=0}^{x}(-1)^i C_{x}^{i} (2^{n-i}-1)^y\ 2^{(n-i)(m-y)}$$

转移是有条件的。当 $i$ 为层左端时，$j=0$。当 $fa_i$ 不存在时，$j=cnt_i$。

最后是统计答案。

若本层的右端不是 $(x,x+1)$，那么贡献就是 $f_{i,0}$。

否则，$f_{i,j}$ 需要乘上其内部连边的方案数。不难发现就是在 $cnt_i$ 个点间任意连边(可以自环)，使得前 $j$ 个点都有连边的方案数，记作 $h(cnt_i,j)$。

类似的容斥，得到

$$h(n,x)=\sum_{i=0}^x (-1)^i C_{x}^{i} 2^{\frac{(n-i)(n-i+1)}{2}}$$

最终对答案的贡献就是 $\sum f_{i,j}h(cnt_i,j)$。

然后是节点 1 的保留节目。注意到如果节点 1 有自环，那么这个自环在新图中也是必须有的，而我们会当做有无均可计算，所以答案需要 $/2$。

恰当的预处理可以做到时间复杂度 $O(n^3)$。

实际上还有 $O(n^2)$ 的原神做法，但是我不会。一定是原神等级太低导致的。