这次UR延续了UR 19的风格，又给大家送上了一场良心的UER难度的UR！

跳蚤电话

from rushcheyo，数据，标程，题解 by mayaohua

良心送分A题~

算法一

我会爆搜！

直接按题目描述的过程 $O(n!)$ 爆搜，可以通过子任务 $1$ ，期望得分 $9$ 分。

算法二

我会状压DP！

使用状压DP， $f[S]$ 表示当前点集为 $S$ 的方案数，转移可以预处理一下。

时间复杂度为 $O(2^nn)$ ，可以通过子任务 $1\sim 2$ ，期望得分 $20$ 分。

算法三

如果没想到DP，但是很有拼劲的话，你应该可以把深度不超过 $3$ 的数据手玩出公式。

可以通过子任务 $5$ ，期望得分 $14$ 分，结合算法二可以得到 $34$ 分。

算法四

考虑靠谱做法。倒着考虑题目的过程，其实就是在一棵树上每次删去一个度为 $1$ 的节点或删去一个度为 $2$ 的节点并合并两个邻接点。

不妨先计算概率，最后再乘回 $(n-1)!$ 。 令 $f_i$ 表示考虑子树 $i$ ，假定节点 $i$ 有一个不可删去的父亲，随机排列能删空子树 $i$ 的概率。那么原来答案显然就是 $(n-1)!\cdot \prod\limits_{i\in son_1}f_i$。

这个DP的转移可以考虑枚举子树 $i$ 中最后一个删去的节点：如果是节点 $i$ ，那么贡献显然是 $\prod\limits_{j\in son_i}f_j$；否则不妨设它是节点 $j\neq i$ ，那么之前需要分别删去两个部分—— $j$ 子树中其它节点及 $i$ 子树中除去 $j$ 子树的部分。第一个部分的贡献显然是 $\prod\limits_{k\in son_j}f_k$，而考虑第二部分，令节点 $i$ 到节点 $j$ 路径上的节点依次是 $a_1=i,a_2,\ldots,a_k=j$ ，那么由于节点 $i$ 的父亲不可删去且节点 $j$ 最后删去，因此删去某个 $a_u$ （ $u < k$ ）时它的度数必定是 $2$ ，且它所有不是 $a_{u+1}$ 的子树都被删空了，那容易看出这部分概率就是 $\prod\limits_{u=1}^{k-1}(\prod\limits_{v\in son_{a_u},v\neq a_{u+1}}f_v\cdot \frac{1}{siz_{a_u}-siz_{a_{u+1}}})$ 。不论哪种情况，因为我们钦定了某个点最后一个删除，最后还要乘上 $\frac{1}{siz_i}$ 。

直接按上面的式子实现，时间复杂度为 $O(n^2)$ ，事实上能通过子任务 $1\sim 5$ ，期望得分 $71$ 分。

算法五

冷静一下，发现算法四里面的式子不少部分可以预处理。具体来说，我们可以让 $g_i=f_i\cdot siz_i$ ，并在第二种情况中枚举节点 $j$ 所在的子树，那么容易得到下面的递推式： $g_i=\prod\limits_{j\in son_i}f_j+\sum\limits_{j\in son_i}g_j(\prod\limits_{k\in son_i,k\neq j}f_k\cdot \frac{1}{siz_i-siz_j}),f_i=g_i \cdot \frac{1}{siz_i}$ 。

上面推导的关键是注意到如果我们选择了子树 $j$ 中节点 $k$ ，那么 $k$ 对子树 $i$ 和子树 $j$ 贡献时，唯一区别就是在 $a$ 序列最前面加了一个节点 $i$ ，因此很容易更新贡献。

精细实现时间复杂度为 $O(n\log n)$ 或 $O(n)$ ，可以通过子任务 $1\sim 6$ ，期望得分 $100$ 分。

算法六

把算法五的DP式子仔细拆开，事实上能得到一个不用DP的做法： $f_i=\prod\limits_{j \in subtree_i}\frac{1}{siz_j}(1+\sum\limits_{k\in son_j}\frac{siz_k}{siz_j-siz_k})$ 。

这样只需要预处理一下逆元就可以简单计算了，时间复杂度为 $O(n)$ ，可以通过子任务 $1\sim 6$ ，期望得分 $100$ 分。

Bonus

这题原来是作为B题的，一开始的版本是有 $q\leq 10^5$ 次询问，每次询问一个点集 $S$ （ $\sum |S|\leq 10^5$ ）作为最后保留的节点集合（而不是现在的只有节点 $1$ 被保留），有兴趣的同学可以自己思考下。

机器蚤分组

from rushcheyo，数据 by nike0good，标程，题解 by mayaohua

感谢matthew99帮助加强。

大家纷纷通过了这题，但是是否记得要证明结论呢？

算法零

或许有某些神奇的搜索能通过子任务 $1$ ？期望得分 $9$ 分。

算法一

很容易看出这是一个最小链覆盖模型：令子串 $a\leq b$ 当且仅当 $a$ 是 $b$ 的子串，这是一个定义在子串集合上的偏序关系，那么就是选择最小数目的链覆盖所有子串。

直接用网络流来求解DAG最小链覆盖，可以通过子任务 $1\sim 2$ ，期望得分 $27$ 分。

算法二

刚刚的做法没有利用题目的特殊性质。根据dilworth定理，最小链覆盖等于最长反链，考虑从这个方向入手。

容易发现我们可以选择某个长度 $len$ 的所有子串作为一个极长反链。可以大胆猜测，对不同的 $len$ 取最大值就是最长反链！

发现这样确实能通过所有样例，让我们来证明一下：

引理1：最长反链长度即为最大的同一长度不同子串个数。

证明：如果存在一个反链中子串长度不全相同，我们下面证明可以得到一个相同长度的串长度全相同的反链。

考虑其中长度最小的串长 $len$ ，如果我们能够找出一个子串 $S[l,l+len-1]$ 在反链中，且 $S[l-1,l+len-2]$ 或 $S[l+1,l+len]$ 不在其中，我们显然可以将 $S[l,l+len-1]$ 换成 $S[l-1,l+len-1]$ 或 $S[l,l+len]$ （这两个串显然都不在原来反链中）而仍然为反链。反复进行这个操作，直到不能调整为止，此时所有长度为 $len$ 的子串均在其中，那显然不可能有其它长度子串，也即此时得到一个串长度全为 $len$ 的相同长度反链。

由上述结论，我们只需要计算出每个长度的不同子串个数，这可以用 SAM 或者 SA 计算。

对每组询问分开构建 SAM 或 SA，时间复杂度为 $O(nq\log n)$ 或 $O(nq)$ ，可以通过子任务 $1\sim 3$ ，期望得分 $48$ 分。

算法三

考虑对多组询问加速。

在算法二的基础上尝试一些数据结构乱搞，比如用回滚莫队加线段树可以做到 $O(n\sqrt q\log n)$ 左右的复杂度。

（或许）可以通过子任务 $1\sim 4$ ，期望得分 $65$ 分。

算法四

当串随机的时候，算法二中得到的串长 $len$ 不会太大。

考虑取一个阈值 $T$ ，只考虑长度 $\leq T$ 的串。对询问离线并对右端点扫描线，这样每次加入 $O(T)$ 个串，用哈希维护下上一次出现位置，并用树状数组每个左端点维护不同子串个数即可。

时间复杂度为 $O((n+q)T\log n)$ ，取 $T=20$ 即可通过子任务 $5$ ，结合算法三，期望得分 $80$ 分。

算法五

基于刚刚的结论优化是很难通过子任务 $6$ 的，我们希望有更强的结论。

通过大胆猜想和用样例验证，我们可以猜测下面的结论：

引理2：最长反链长度 $\geq k$ 当且仅当长度为 $n-k+1$ 的子串两两不同。

证明：充分性是显然的——只需要取所有长度为 $k$ 的子串即可。

考虑证明必要性。根据引理1，我们只需要考虑所有长度为某个固定 $len$ 的子串，那么若最长反链长度 $\geq k$ ，显然有 $len\leq n-k+1$ 。

假设存在两个长度为 $n-k+1$ 的子串 $S[a,a+n-k]$ 和 $S[b,b+n-k]$ （ $a < b$ ）相同，那么 $\forall 0\leq i \leq n-k+1-len$ ，均有 $S[a+i,a+i+len-1]=S[b+i,b+i+len-1]$ 。于是，长度为 $len$ 的不同子串个数不会超过 $(n-len+1)-(n-k+1-len+1)=k-1$ ，矛盾。

故所有长度为 $n-k+1$ 的子串互不相同。

由上述结论，答案即为 $|S|-\max\limits_{1\leq i< j\leq |S|}lcp(S[i,],S[j,])$ 。

直接每组询问分开用 SAM 或 SA 计算，时间复杂度同样为 $O(nq\log n)$ 或 $O(nq)$ ，可以通过子任务 $1\sim 3$ ，期望得分 $48$ 分。

算法六

考虑快速解决多组询问，这可以对算法五用数据结构优化。

在后缀树上对后缀集合进行启发式合并，每次合并两个不同子树中的后缀集合 $S_1$ 和 $S_2$ ，提取出后缀对 $(x,y)$ （ $x < y$ ）使得 $x\in S_1,y\in S_2$ 或 $x\in S_2,y\in S_1$ 且 $x,y$ 在 $S_1\cup S_2$ 中相邻。容易发现对询问有用的 $(i,j)$ 一定会是这样提取出的 $(x,y)$ ，而这样的 $(x,y)$ 只会有 $O(n\log n)$ 对。

那么对询问离线，对右端点扫描线加入这些 $(x,y)$ 对，并用线段树维护每个左端点的答案即可。

时间复杂度为 $O(n\log^2n+q\log n)$ ，可以通过子任务 $1\sim 6$ ，期望得分 $100$ 分。如果用 SAM+LCT 代替后缀树上启发式合并，也可以得到相同复杂度做法。

金坷垃

from Infleaking，数据，标程，题解 by Infleaking

算法一

肥力第 $i$ 小的当然是 $a_i$ 啦！甚至不用排序，直接输出 $a_i+m/2$ 。

可以通过子任务 $1$ ，期望得分 $3$ 分。

算法二

我们知道一个经典结论， $n$ 个 $[0,1]$ 随机实数第 $i$ 小的期望是 $\frac i{n+1}$ ，于是我们套入这个题里面，答案就是 $a+\frac{mi}{n+1}$ 。

可以通过子任务 $2$ ，结合算法一期望得分 $18$ 分。

算法三

这个题甚至都没法暴力！

问题来了，现在我推出了一个式子，我要怎么才能知道我没写错呢？测样例！

借助算法二的结论，我们搞到了一个显然正确的暴力：

按照端点分段，枚举每个值在哪一段中，利用算法二，我们就可以得到在这种情况下的答案。把所有情况乘上出现的概率求和就是答案了。

时间复杂度 $O(n^n)$ ，可以通过子任务 $3$ ，结合算法一、二期望得分 $34$ 分。

算法四

假设我们知道 $f_i(x)$ 表示第 $i$ 小的数大于$x$的概率，那么显然 $ans_i=\int f_i(x)dx$ 。

通过枚举哪些数是小于 $x$ 的，我们可以得到一个 $f_i(x)$ 的表达式 $f_i(x)=\sum_{|S|=i-1}(\prod P(s_j)\prod (1-P(a_{t_j})))$

（ $T$ 为 $S$ 的补集， $P(i)$ 是关于 $x$ 的函数且 $P(i)(x)=a_i < x$ 的概率）。

这个 $P$ 是一个分段的直线，因此 $f_i(x)$ 会是一个分段的多项式，枚举端点然后直接DP维护 $f_i$ 的每一项系数。

时间复杂度 $O(n^4)$ ，可以通过子任务 $3\sim 4$ ，结合算法一、二期望得分 $55$ 分。

算法五

聪明的同学已经发现了，相邻的两个端点之间只有少数的 $P(i)$ 是会变的，我们可以直接利用上一个端点的DP值快速计算出下一个。具体来说就是撤销原来的 $P(i)$ 对于 $f$ 的影响，假装这是最后加入DP的值，然后倒着算一遍把之前的DP值求出来，再加入新的 $P(i)$ 。

时间复杂度 $O(n^3)$ ，可以通过子任务 $3\sim 5$ ，结合算法一、二期望得分 $69$ 分。

算法六

瓶颈在于这个积分，这使得我们不得不求出所有的 $f$ 然后一个一个算。

观察最初的式子 $f_i(x)=\sum_{|S|=i-1}(\prod P(s_j)\prod (1-P(a_{t_j})))$ ，我们知道多个函数乘积高阶导数就是尝试将求导分配到每一个乘积里面，然后对每一种方案求和。观察到 $P(i)=\frac {x-a_i}m$ 或者为常数，其一阶导是 $\frac1m$ ，如果我们把后面的尾巴去掉，就可以得到 $g_i(x)=\sum_{|S|=i-1}\prod P(s_j)$ 是 $G(x)=\prod P(i)$ 的高阶导数乘上一个系数。

考虑其组合意义： $f_i$ 是恰好有 $i$ 个数满足条件的情况之和，而 $g_i$ 是枚举有 $i$ 个数满足条件，对其他数没有要求的所有情况之和，因此可以得到其关系 $g_i=\sum \binom{j}{i}f_j$ ，因此我们可以用 $g_i$ 反解出 $f_i$ 。

此时，我们只需要对相邻两个端点，求出 $G(x)$ 的高阶导数在端点处的点值即可，这是一个卷积的形式，可以用FFT解决。而 $G(x)$ 可以通过上一段区间的 $G(x)$ 乘除少量二项式得到。

相邻的两个端点之间需要一次卷积来计算答案，因此时间复杂度是 $O(n^2\log n)$ 的，可以通过子任务 $1\sim 7$ ，期望得分 $100$ 分。如果不幸常数写大了，可能只有 $74$ 分。