这次排名还不错，但是

Unrated

于是 Rating+=0 QwQ

T1 闯关

本题思路小总结：

• 由题意，九条可怜会优先选择重要度较低的关卡且优先选择编号小的关卡。
• 那么容易发现，当九条可怜的通关编号顺序是上升的，可以设这些关卡重要度相同，直到出现一个逆序对。
• 我们将初始重要度设为 $1$，从通关顺序序列的开头为每个关卡赋上它们的重要度，遇到逆序对则将重要度 $+1$ 后继续赋重要度。这样我们就可以得到关卡重要度的序列。
• 我们开始考虑求出难度：遍历每个关卡。当该关卡重要度与上一个关卡的重要度不同时，其难度=重要度，并标记该难度已被求出。
• 最后将所有未被求出的难度按顺序为每个关卡赋值，输出答案序列。

100pts

T2 动物园

本题思路小总结：

• 三种动物循环克制且初始等概率出现，由对称性可知合并时主场方最终存活的概率为 $\frac{2}{3}$，客场方为 $\frac{1}{3}$。
• 用带权并查集维护当前笼子（集合），每个节点 $x$ 的权值 $w_x$ 表示从 $x$ 到其集合根的概率比例，根额外维护 $val_{root}$ 作为该集合的基准概率。
• 初始每个节点 $w_x=1$，每个根 $val_{root}=1$，表示任意原始动物在当前笼子中存活的概率为 $1$。
• 合并 $1\ u\ v$：找到根 $ru,rv$，令新根为 $ru$，更新 $val_{ru}=val_{ru}\times \frac{2}{3}$，$val_{rv}=val_{rv}\times \frac{1}{3}$，将 $rv$ 的父亲设为 $ru$，并设 $w_{rv}=val_{rv}\times inv(val_{ru})$。
• 查询 $2\ u$：先路径压缩得到根 $r$，则 $u$ 中原始动物存活的概率为 $prob=val_r \times w_u$，答案即为 $prob \times 3^n \bmod 998244353$。
• 路径压缩时按根到叶顺序累乘权值，确保 $w_x$ 始终是到当前根的正确比例。
• 所有运算均在模 $998244353$ 下进行，$inv$ 使用快速幂计算逆元。

T3 树

依旧图论黑洞。

0pts

本题思路小总结：

• 先换根 DP 求出每个节点作为根时的 $dp_0(u)$（根不选）和 $dp_1(u)$（根选），及初始答案 $ans=\max(dp_0(1),dp_1(1))$，标志 $flag=[dp_1(1)>dp_0(1)]$。
• 每次操作给定 $k$，新树由基树 $T(k)$ 的每个节点挂一个 $T_{i-1}$ 副本构成。
• 若 $flag=1$，新答案 $ans’=ans\cdot n$，且 $flag’=0$；否则 $ans’=ans\cdot n+ans_0$（$ans_0$ 为初始答案），$flag’=[dp_1(k)>dp_0(k)]$。
• 每次操作后输出 $ans$，所有运算对 $998244353$ 取模。
• 复杂度 $O(n+m)$。

订正