题解：[[2024.10.13 模拟赛]] ## 一般图最小匹配 #序列dp #排序 有 $n$ 个数，第 $i$ 个数为 $a_i$。需要选择 $m$ 对数，每次选择没有被选择过的数 $(i,j)$，该次权值则为 $|a_i-a_j|$。求 $m$ 次选择之后的最小权值。 ## 重定向 #贪心 #优先队列 有长度为 $n$ 的序列 $a$，第 $i$ 个数为 $a_i$。可能会有若干位置上没有数，表示为 $a_i=0$。现在需要从 $n$ 个数当中删除任意一个数（可以删除空的位置），然后对于剩下的空的位置，可以填入 $[1,n]$ 的数，但是需要保证填写完之后 $a$ 没有重复的数，且字典序最小。输出填完后的序列。 ## 斯坦纳树 #并查集 #树 给定一张图 $G=<V,E>$ 和点集 $V_1$，需要找到原图的一张子图，涵盖点集 $V_1$ 且连通，边权和尽量小。有一个问题：给定一棵树 $G$，每次给出点集 ${} V_1 {}$，求 $V_1$ 在 $G$ 上的斯坦纳树边权和。 牛牛不会做这个问题，于是提出乱搞做法：建立新的完全图 $F'$，每一个点都对应 $V_1$ 的一个点，两个点的边权为 $V_1$ 对应的点在 $G$ 的树上距离，最后将 $F'$ 的最小生成树作为答案。 牛牛想要知道，这种乱搞算法在什么情况下是正确的。给出排列长度为 $n$ 的排列 $p$，牛牛想要知道对于 $i$ $(1\le i\le n)$ 在点集 $V_i=\{p_1,p_2,\cdots,p_i\}$ 上的正确性。 ## 直径 #快速幂 #递推 #树 给定 $n,k,p$，求 $n$ 个点组成的无标号无根树当中，直径长度为 $k$ 且有 $p$ 条直径的树的数量有多少，答案对 $998244353$ 取模。