20260302紫题训练总结

A - Secret Message

考虑把前 \(n-1\) 小的边拿出来，如果不联通，直接输出，否则去枚举每一条非树边，计算把这一条边加上后的答案。
具体的，当前枚举到的非树边的两个定点在树上的路径中的边是不能删除的，把这些边长度临时减去 \(inf\)，然后求最所有树边的最小值。这个可以用树剖维护。
现在我们考虑了加上一条非树边的情况，但实际上可以不止加一条。容易发现，删两条的最优方案为把第 \(n-2\) 和 \(n-1\) 条边删掉，把第 \(n\) 和 \(n+1\) 条边加上（排序后）。如果不合法，一定不优，所以可以直接和原答案取 \(min\)。

B - Sugoroku

简单题，但是卡常。
设 \(f_i\) 表示走到 \(i\) 且存活的概率。

\[\begin{array}{l} f_i=\sum_{j=1}^mf_{i-A_j}\times\frac1m\\ f_i=\frac1m\times\sum_{j=1}^if_{i-j}\times[j\in A] \end{array} \]

然后分治 \(NTT\) 优化即可。

C - 马赛克

简单题。题解。