记 GESP 八级 202409

 --- 直接看编程题。话不多说，上题面。 [T1：手套配对](https://www.luogu.com.cn/paste/0fj749gb) [T2：美丽路径](https://www.luogu.com.cn/paste/5mzavwsx) ## T1 本题为数学题，但是直接去推式子还是有一定难度的。 ~~实际上可以**瞪眼法**先推一个“看起来比较正确”的式子。这个时候大概率会有问题，可以再用 `dfs` 打一张绝对正确的表（我用的是 $n=5,m\in[1,10],k\in[1,5]$ 的表）。随后看看式子和表有什么区别（比如多乘了 $2$ 的几次方，少了一项组合数之类的。）~~ 相信我这么写大家都不会同意的，所以补个场后证明。 首先一个显然的结论：当 $m<2\times k$ 时，无可行方案，因为 $k$ 对手套至少需要选择 $2k$ 件手套才够。 排除这种情况，我们逐点考虑。首先在 $n$ 对手套中选择完整 $k$ 对的方案数为 $C_n^k$。还剩下 $m-2\times k$ 件手套是可选的，而这些手套可以从剩下的 $n-k$ 对手套中选择。左右手比较难办，我们暂时设剩下这些手套都只有左手，那么方案数就要再乘上 $n-k$ 件手套中选 $m-2\times k$ 件手套的方案数，也就是 $C^{m-2\times k}_{n-k}$。然后补上每一件手套都有左右手两种可能，就是再乘 $2^{m-2\times k}$。 最后放出结论，答案为： $$\begin{cases} \left(C^k_n\times C^{m-2\times k}_{n-k}\times 2^{m-2\times k}\right)\bmod (10^9+7)&\text{,}\ m-2\times k\geq0\text{;} \\ 0\quad&\text{, otherwise.} \end{cases}$$ 组合数和 $2$ 的幂用递推公式预处理即可，数据范围再大组合数可以用模意义下的乘法逆元或者 Lucas 定理处理。时空复杂度 $O(n^2)$。 ## T2 显然本题为树形 dp。按照树形 dp 的套路，我们令根为 $1$，$ans(i)$ 为以 $x$ 为根的子树中的最长美丽路径长度，$dp(i)$ 为以 $x$ 为根的子树且路径的一端为 $x$ 的最长美丽路径长度，则答案为 $ans(1)$。容易得到转移方程： $$dp(x)=\begin{cases} 1 & \text{,}\ son_x=\varnothing\text{;} \\ \max\limits_{y\in son_x\operatorname{and}c(x)\neq c(y)}\{dp(y)+1\} \quad &\text{, otherwise.} \end{cases}$$ $$ans(x)=\begin{cases} 1 & \text{,}\ son_x=\varnothing\text{;} \\ \max\{\max\limits_{y\in son_x}\{ans(y)\},maxlen+seclen+1\} \quad &\text{, otherwise.} \end{cases}$$ 其中 $maxlen,seclen$ 分别为异色儿子 $y$ 中 $dp(y)$ 的（非严格）最大、次大值。 翻译：若节点 $x$ 为叶子节点，则 $dp(x)=ans(x)=1$；否则 $dp(x)$ 为其所有异色子节点 $y$ 中最大的 $dp(y)+1$，$ans(x)$ 为其所有子节点 $y$ 中最大的 $ans(y)$，再与其所有异色子节点 $y$ 中 $dp(y)$ 的（非严格）最大、次大值之和加一取最大值。 用 dfs 转移，时间复杂度 $O(n)$。 ## 后记 ~~估分 $90pts$ 以上嘿嘿。~~ 看了官网答案，vocal，I AK GESP 8级！！！